BOJ - 2841. 외계인의 기타 연주

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력 1

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

예제 출력 1

9

사용할 자료구조

• 프렛을 누를때는 push 해야하고 프렛에서 손가락을 땔 때는 pop해가면서 누적해가는 문제이므로 스택을 사용해야한다고 떠올렸습니다. (+가장 최근에 입력된 top 원소를 갖고 비교하면 되는 문제이기 때문에)
• 기타에는 6개의 줄이 있다하여 6개의 스택을 배열로 구현하였습니다.

풀이 과정

1) 루프를 반복할때마다 몇 번 기타줄인지 (stackIndex), 해당 기타줄의 어떤 버튼을 클릭했는지(buttonIndex)를 입력받아주었습니다.

2) 해당 기타줄에서 아무것도 누르고 있지 않을 경우 (스택이 비어있는 경우)

• 무조건 버튼 번호를 삽입해줍니다.

3) 만약 현재 누르고 있는 버튼과 같은 번호가 들어올 경우 (스택의 탑과 같은 경우)

• 다른 버튼을 누를 필요도 없고, 현재 번호에서 손을 땔 필요도 없으므로 카운트하지 않고 바로 다음 루프로 이동하면 됩니다.

4) 만약 현재 누르고 있는 버튼보다 높은 번호가 들어올 경우 (스택의 탑보다 들어오려는 값이 큰 경우)

• 해당 버튼을 눌러야하므로 버튼 번호를 삽입해줍니다.

5) 만약 현재 누르고 있는 버튼보다 낮은 번호가 들어올 경우 (스택의 탑보다 들어오려는 값이 작은 경우)

• 새롭게 누르려는 번호가 직전 버튼보다 더 커질때까지 스택에서 빼주면 됩니다.
• 스택에서 빼는건 손가락을 뗀다는 의미와 같으므로 하나를 뺄 때마다 카운트 증가
• 계속 빼다가 만약 직전 버튼번호와 같을 경우에는 더 이상 할 게 없으므로 다시 루프로 돌아갑니다.
• 직전 버튼 번호를 찾았으면 그 위에 새롭게 누른 버튼 번호를 쌓아올립니다.

시간 복잡도

• 스택 삽입 삭제는 O(1)만큼 걸리는데, n만큼의 루프를 도므로 시간복잡도는 O(N) 입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    //기타줄은 총 6개
    stack<int> guitar[7];

    int n,p; //p는 필요없는 수인듯?
    cin>>n>>p;
    int answer = 0;
    for(int i=0;i<n;i++){
        int stackIndex, buttonIndex;
        cin>>stackIndex>>buttonIndex;

        if(guitar[stackIndex].empty()){ //ok
            guitar[stackIndex].push(buttonIndex);
            answer++;
        }else{
            if(guitar[stackIndex].top()==buttonIndex){ //ok
                continue;
            }else if(guitar[stackIndex].top()<buttonIndex){ //ok
                guitar[stackIndex].push(buttonIndex);
                answer++;
            }else if(guitar[stackIndex].top()>buttonIndex){
                while(!guitar[stackIndex].empty() && guitar[stackIndex].top() > buttonIndex){
                    guitar[stackIndex].pop();                    
                    answer++;
                }

                if(!guitar[stackIndex].empty()&&guitar[stackIndex].top()==buttonIndex){
                    continue;
                }else{
                    guitar[stackIndex].push(buttonIndex);
                    answer++;  
                }

            }
        }
    }
    cout<<answer;

    return 0;
}