[백준] 프린터 큐_1966_자바

안녕하세요😎 백엔드 개발자 제임스입니다 :)
오늘은 카테고리 큐에 해당하는 문제 [프린터 큐]에 대해서 포스팅하도록 하겠습니다. 난이도가 그렇게 높은 문제는 아닙니다. 큐만 잘 활용한다면, 간단한 문제인데요. 저는 문제를 제대로 이해하지 못한 탓에 꽤나 애먹었습니다. 문제에 대한 자세한 정보는 아래 링크에 있습니다.
https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

---

Problem

---

독특한 프린터 기기가 있습니다. 이 프린터 기기는 중요도에 따라서 문서를 인쇄합니다. 보통의 프린터 기기는 인쇄하고자 하는 문서를 입력받은 '순서대로' 출력합니다. 즉, '먼저 요청된 문서를 먼저 인쇄한다.', FIFO-First In, First Out 규칙인 Queue 자료구조 형태로 진행됩니다. 그러나 이 독특한 프린터 기기는 그렇지 않습니다. 조건은 아래와 같습니다.

1. 프린터 기기에서 현재 출력할 문서의 중요도를 확인한다.
2. 나머지 문서들 중 현재 문서보다 높은 중요도를 가진 문서가 있다면, 현재 출력할 문서를 가장 프린터기 가장 뒤로 보낸다.
3. 만약 현재 출력할 문서가 가장 높은 중요도를 가졌다면 인쇄를 진행한다.

위 내용에 대해서 예를 들자면, 프린터 기기에 문서가 A, B, C, D로 있습니다.(A가 가장 앞에 있습니다.)
이때 각 문서들은 2, 1, 4, 3이라는 중요도를 갖습니다. 따라서 인쇄를 진행하면, 중요도가 2인 A는 프린터 기기의 가장 뒤로 이동합니다. B, C, D, A 형태가 되는 것입니다. 다음에 진행될 B 문서도 마찬가지겠지요? 이렇게 되는 이유는 알다시피 C가 중요도 4로 가장 높기 때문입니다.
이러한 방식으로 진행된다면, C, D, A, B 순으로 인쇄됩니다. 이제까지 프린터에 대한 설명이었습니다.
이제 문제를 설명하자면, 중요도를 가진 문서들이 위 같은 프린터 기기에 있을 때 특정 위치에 문서가 몇 번째로 출력되는지 알아보는 것입니다. 위에서 프린터 기기에 대해서 설명할 때 들었던 예시로 다시 예를 들어보겠습니다.
중요도가 각각 2, 1, 4, 3 인 A, B, C, D에서 인덱스 3번에 위치한 문서가 몇 번째로 출력되는지 알아보는 문제라고 생각하면 되겠습니다. 결과는 두 번째로 출력되니, 2가 됩니다. 이제 풀이를 진행하도록 하겠습니다.

---

풀이 아이디어

---

해당 문제를 풀기 위해서는 Queue를 사용해도 좋고, 그렇지 않아도 됩니다. 사실상 구현에 가까운 문제입니다.
만약 Queue를 활용해서 푼다면, 인덱스로 컬렉션을 다루는 것이 아니기 때문에 여러 개의 queue가 필요할 수 있습니다. 저는 처음 문제를 접했을 때 index를 활용해야겠다고 생각했습니다. 따라서 ArrayList로 풀이를 진행했는데요. 하지만 문제 자체에 반례가 많아서 코드가 길어지거나 생각해야 할 조건이 많아졌습니다.
처음 이 포스팅을 시작할 때 문제를 잘못 이해했다고 언급했습니다. 이제 그 이유를 말하겠습니다. 저는 문서 중 가장 앞에 있음에도 중요도가 가장 높은 수가 아니라면 큐의 제일 뒤로 보냈급니다. 이어서 중요도가 가장 높은 문서를 제일 앞으로 이동시켰습니다. 그리고 출력 했습니다(큐에서 제거했다는 의미입니다.) 사실 어떻게 생각해보면, 의미상 비슷합니다. 하지만 이러한 방법에는 까다로운 조건이 많았습니다. 가령 위치와 중요도에 따라 문제에서 주어진 찾고자 하는 문서의 위치가 계속 바뀌었는데요. 어떠한 경우에는 -1이 되거나 어떠한 경우에는 -2 또는 0만큼 이동하게 되었습니다. 즉, 상황에 따라 반례가 많아지게 되었습니다.
그럼 어떻게 문제를 해결하면 좋을까요?

테이블 안에 숫자는 문서의 중요도를 나타냅니다.

사실 너무나 간단합니다. 위에 그림과 같은 Queue가 있습니다. 그리고 우리는 인덱스 2번에 해당하는 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 즉, 중요도가 3인 문서의 출력 순서를 구합니다.
먼저 가장 앞에 있는 문서의 중요도가 가장 큰 숫자인지 체크합니다. 가장 높지 않다면 Queue에서 Poll을 하고, 다시 add를 해주면 됩니다. 그렇다면 문서는 2, 3, 4, 1이 되는데요.

해당 Queue에서 4가 가장 높으므로, 동일하게 진행했을 때 4, 1, 2, 3으로 재배치됩니다. 중요도가 가장 높은 문서가 제일 앞으로 왔으니 이제 poll을 하고, count는 1 증가하게 됩니다.(count는 문서가 몇 번째 출력되는지 나타내는 변수입니다.) 그럼 이제 Queue에는 1, 2, 3 이 남았겠죠? 위에 내용처럼 동일하게 진행합니다. 그렇다면 3이 출력될 때 count가 2라는 것을 알 수 있습니다.
문제가 이렇게만 해서 끝나면 좋겠지만, 체크해야할 반례 상황이 있습니다. 우리가 알고자하는 문서의 중요도와 동일한 중요도가 존재할 때입니다.

문서의 중요도가 적힌 Queue

ㅁ우리는 위에 그림에서 0번째에 위치한 중요도 1인 문서가 몇 번째에 인쇄되는지 알고 싶다고 가정하겠습니다. 이때 결과는 5번째라는 결과를 얻어야 합니다. Queue 컬렉션은 index만을 따로 다루지 않기 때문에, 저 많은 1 중에 우리가 원하는 결과의 문서가 몇 번째로 출력되는지 알 수 없습니다. (단지, 같은 중요도가 인쇄되었을 때의 결과로 해결한다면 결과는 2가 나옵니다!)

---

이 상황을 해결하기 위해서 Queue를 하나 더 생성합니다. 이렇게 만든 Queue에는 index를 저장합니다.

index 정보가 들어간 Queue

원리를 이해하기 위해 다시 돌아와서 중요도가 적힌 Queue를 보겠습니다. 가장 먼저 0번째 문서보다 높은 중요도를 가진 문서가 있기 때문에 0번째 문서는 제일 뒤로 갑니다. 이때 index 정보가 들어간 Queue의 0번째 데이터도 제일 뒤로 보냅니다.

문서의 중요도가 적힌 Queue

 

index 정보가 들어간 Queue

이와 같이 진행하면서 찾고자하는 문서가 출력될 때, index가 맞는지 체크하면 원하는 결과를 얻을 수 있습니다. 위에 예시에서 0번째의 문서는 5번째로 출력하는 것을 알 수 있습니다.

---

코드 작성

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 128ms
public class PrinterQueue_1966 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        // 테스트 케이스 입력
        int testCase = Integer.parseInt(br.readLine());

        Queue<Integer> queue = new LinkedList<>(); // 중요도가 들어있는 큐
        Queue<Integer> indexOfQueue = new LinkedList<>(); // 위치가 저장된 큐

        for (int i = 0; i < testCase; i++) {

            st = new StringTokenizer(br.readLine());

            int countOfChar = Integer.parseInt(st.nextToken()); // 문자의 수
            int indexOfChar = Integer.parseInt(st.nextToken()); // 찾고자하는 문자의 위치

            st = new StringTokenizer(br.readLine());
            int index = 0; // indexOfQueue에 들어갈 index 정보
            int count = 0; // 출력 순서

            // 각 큐에 중요도와 인덱스 정보를 저장
            for (int j = 0; j < countOfChar; j++) {
                queue.add(Integer.parseInt(st.nextToken()));
                indexOfQueue.add(index++);
            }

            while (queue.size() > 0) {

                // 큐에서 가장 높은 중요도의 값을 찾음
                int max = queue.stream().mapToInt(n -> n).max().getAsInt();

                // 현재 인쇄할 문서의 중요도가 가장 높지 않을 때
                if (queue.peek() != max) {
                    // 각 큐에서 출력할 값을 제일 뒤로 이동
                    queue.add(queue.poll());
                    indexOfQueue.add(indexOfQueue.poll());
                    
                } else { // 인쇄할 문서의 중요도가 가장 높을 경우

                    // 인쇄할 문서의 인덱스 정보가 찾고자하는 인덱스와 동일할 때
                    // count에 1을 더하고, 출력한다. (값 저장 후 while문 종료)
                    if (indexOfQueue.peek() == indexOfChar) {
                        
                        count++;
                        sb.append(count).append('\n');
                        break;
                        
                    } else { // 동일하지 않을 때
                        
                        // 각 큐에서 출력(인쇄)하고, 순서(count)에 +1을 한다.
                        queue.poll();
                        indexOfQueue.poll();
                        count++;
                    }
                }
            }
        }

        System.out.println(sb);
    }
}