[Java] Baekjoon 1966. 프린터 큐

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

코드

import java.io.*;
import java.util.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());
            int printCount = 0;
            boolean nowNodeIsMax;

            LinkedList<int[]> printerQueue = new LinkedList<>();
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                printerQueue.offer(new int[]{i, Integer.parseInt(stringTokenizer.nextToken())});
            }

            while (!printerQueue.isEmpty()) {
                nowNodeIsMax = true;
                int[] nowNode = printerQueue.poll();
                for (int i = 0; i < printerQueue.size(); i++) {
                    int[] comparisonNode = printerQueue.get(i);
                    if (nowNode[1] < comparisonNode[1]) {
                        printerQueue.offer(nowNode);
                        nowNodeIsMax = false;
                        break;
                    }
                }
                if (nowNodeIsMax) {
                    printCount++;
                    if (nowNode[0] == M) {
                        break;
                    }
                }
            }
            bw.write(Integer.toString(printCount));
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }
}

풀이

int 배열을 원소로 지닌 LinkedList를 구현하여 접근했다. LinkedList의 원소인 int 배열에는 문서가 몇 번째에 놓여 있는지를 나타내는 위치 값(index)과 문서의 중요도(importance)를 원소로 가지고 있다.

printerQueue.offer(new int[]{i, Integer.parseInt(stringTokenizer.nextToken())});

이 코드에서 LinkedList인 printerQueue에 값이 할당된다.

while 반복문을 돌며 printerQueue의 맨 왼쪽에 위치한 문서를 poll하여 꺼낸 뒤, nowNode에 할당하고 중요도(nowNode[1])를 for 반복문을 사용해서 printerQueue에서 꺼낸 문서(comparisonNode)의 중요도(comparisonNode[1])와 비교를 진행한다.

만약 nowNode의 중요도가 comparisonNode의 중요도 보다 작다면 중요도가 높은 문서가 뒤에 위치한 것이므로, nowNodeIsMax를 false로 바꾸고 nowNode를 printerQueue에 offer한다. 이렇게 하면 2번 조건(나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.)을 만족시킬 수 있다.

하지만 for 반복문을 모두 수행했는데도 nowNodeIsMax가 true라면 이는 nowNode의 중요도가 가장 높다는 것을 의미하기에 printCount의 값을 1 증가시킨다. 여기서 만약 nowNode의 위치 값(nowNode[0])이 입력으로 주어진 M과 같다면 우리가 구하고자 했던 문서이므로 while 반복문을 탈출하여 printCount 값을 출력한다.

소감

처음에 무작정 Queue를 구현하여 문제를 풀어보려고 했으나, Queue에서 get 메서드를 사용할 수 없다는 점을 인지하고 좀 애를 먹었다. get을 통한 반복문을 돌릴 수가 없기 때문에 모든 원소를 poll하여 비교하고 다시 offeer하고 해야하는데 이 과정에서 시간이 조금 끌렸다. 그러다가 그냥 LinkedList로 풀어야겠다는 생각이 들어 코드를 작성해봤는데 다행히도 시간 초과가 나거나 그런 불상사는 일어나지 않았다. 애초에 Queue가 LinkedList로 구현되는데 괜한 걱정을 했나 싶은 생각도 들었다.