백준 2841번 외계인의 기타 연주 :: 마이구미

이번 글은 백준 알고리즘 문제 "외계인의 기타 연주" 를 다뤄본다.

문제 접근법은 스택을 활용한다.

정답 비율과 제출수를 보면 어려운 문제에 속한다.

하지만 문제를 이해하기 어려운 것이지, 쉬운 문제로 해당된다.

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

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

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

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

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

본인은 기타를 칠 줄 몰라서 문제를 이해하기 힘들었다.

손가락이 5개이기 때문에, 5개를 모두 누르고 있는 경우도 생각해보고 그랬다.

하지만, 이런 경우는 제목 선정에 이유가 있었다.

외계인이기 때문에, 손가락이 수십억개이고, 문제에서도 알려주고 있었다.

예제를 이해하면, 문제를 이해할 수 있다.

7 15
1 5 => 1회
2 3 => 1회
2 5 => 1회
2 7 => 1회
2 4 => 3회 => 3번, 5번 플렛 떼고 4번 플렛 누름
1 5 => 1회 => 눌려있음.
1 3 => 2회 => 5번 플렛 떼고 3번 플렛 누름

각 줄의 대해 플렛 번호를 오름차순으로 스택에 쌓고, top보다 작은 수가 온다면, pop을 하면 되는 것이 보일 것이다.

결과적으로, 본인은 줄의 번호를 인덱스라고 생각하고, 플렛의 번호를 스택이라고 생각했다.

코드로 나타내면 아래와 같다.

Stack<Integer>[] stack = new Stack[7];
for (int i = 1; i <= 6; i++) {
    stack[i] = new Stack<Integer>();
    stack[i].push(0); // 아래 참고
}

// 1 5 => stack[1] = 5
// 2 3 => stack[2] = 3
// 2 5 => stack[2] = 3 5

그 후, 해당 줄에 대한 스택의 top과 다음 플렛 번호를 비교하면서 스택의 push, pop을 이용한다.

for (int i = 1; i < n; i++) {
    int ln = sc.nextInt();
    int fn = sc.nextInt();

    while (stack[ln].peek() > fn) {
        stack[ln].pop();
        ans++;
    }

    if (stack[ln].peek() != fn) {
        stack[ln].push(fn);
        ans++;
    }
}

while문이 손가락을 떼는 행위이고, 아래 if문이 누르는 행위라고 보면 된다.

누르는 행위는 이전에 눌렀을 경우가 있기 때문에 위와 같은 조건을 준 것이다.

*스택이 비어있을 경우에 대한 편의를 위해 미리 스택 초기화 작업 시 0을 넣어두는 작업을 했다.

private void solve() {
        int n = sc.nextInt();
        int f = sc.nextInt();
        int ans = 1;
 
        Stack<Integer>[] stack = new Stack[7];
        for (int i = 1; i <= 6; i++) {
            stack[i] = new Stack<Integer>();
            stack[i].push(0);
        }
 
        stack[sc.nextInt()].push(sc.nextInt());
 
        for (int i = 1; i < n; i++) {
            int ln = sc.nextInt();
            int fn = sc.nextInt();
 
            while (stack[ln].peek() > fn) {
                stack[ln].pop();
                ans++;
            }
 
            if (stack[ln].peek() != fn) {
                stack[ln].push(fn);
                ans++;
            }
        }
        System.out.println(ans);
    }

백준 알고리즘 2841번 외계인의 기타 연주 전체 소스 

https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/2841.java