[BOJ] 백준 2841번: 외계인의 기타 연주

https://www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

 

문제

 

입력

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

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

 

출력

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

 

난이도

실버 1

 

Sol

스택 6개를 기타의 1번 줄부터 6번 줄이라고 가정하고, 누르고 있는 프렛의 번호를 스택에 저장한다

 

1. line은 눌러야 하는 줄의 번호이고, fret은 그 줄에서 눌러야 하는 프렛의 번호이다. 1번 스택부터 6번 스택이 스택 배열 0번 인덱스부터 5번 인덱스까지 저장되기 때문에 line 입력받을 때마다 -1 처리를 했다

2. 만약 해당 줄을 누르고 있는 손가락이 없다면 바로 fret을 line번 스택에 추가하고, 조작 횟수를 증가시킨다

 

3. 만약 fret보다 큰 프렛을 누르고 있는 손가락이 존재한다면 line번 스택에서 제거하고, 조작 횟수를 증가시킨다. 해당 과정은 fret보다 큰 프렛을 누르고 있는 손가락이 없을 때까지 반복해야 하기 때문에 while문에 작성했다.

 

4. fret보다 작은 프렛을 누르고 있는 손가락이 존재한다면 굳이 손가락을 뗄 필요 없이 line번 스택에 fret을 추가하고, 조작 횟수를 증가시킨다

 

(코드의 간결함을 위해 2번 코드와 4번 코드의 if문을 한번에 작성했다.)

주어진 모든 음에 대해 1번부터 4번까지의 과정을 반복한 뒤 최종적으로 손가락을 움직인 횟수 count를 출력한다.

 

public class BOJ2841 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(token.nextToken()); // 멜로디에 포함되어 있는 음의 수
        int P = Integer.parseInt(token.nextToken()); // 한 줄에 있는 프렛의 수

        Stack<Integer>[] strings = new Stack[6];
        for(int i=0; i<6; i++){
            strings[i] = new Stack();
        }

        int count = 0;

        for(int i=0; i<N; i++){
            token = new StringTokenizer(bf.readLine());
            int line = Integer.parseInt(token.nextToken()) - 1;
            int fret = Integer.parseInt(token.nextToken());

            while (!strings[line].isEmpty() && strings[line].peek() > fret) {
                strings[line].pop();
                count++;
            } // fret을 누른 음을 연주하기 위해 fret보다 큰 프렛을 누르고 있는 손가락을 모두 떼어야 한다

            // 1. fret보다 작은 프렛을 누르고 있는 손가락이 존재한다면 굳이 손가락을 떼지 않고 fret을 눌러도 된다
            // 2. 해당 줄을 누르고 있는 손가락이 없다면 바로 fret을 눌러도 된다
            if ((!strings[line].isEmpty() && strings[line].peek() < fret) || strings[line].empty()) {
                strings[line].add(fret);
                count++;
            }
        }

        System.out.println(count);
    }
}

 

😅

스택 배열이 잘 만들어졌는지 확인하려고 생성할 때 초기값을 넣어보고 출력해봤었는데, 출력문만 지우고 초기값 설정 코드를 지우지 않아 백준에서 계속 오답 처리가 됐었다.. 테스트 후 필요 없는 코드를 잘 지웠나 꼼꼼하게 확인해야겠다.

 

스터디원이 ArrayDeque를 사용했길래 서치해봤는데, Stack보다 ArrayDeque의 성능이 더 좋다고 한다(스레드를 사용하지 않는다면) 생각해보니까 큐 관련한 자료형의 사용법을 다 잊은 것 같다.. 이번주 내로 ArrayDeque를 다시 공부해야 될 것 같다