[BOJ] 백준 1966 - 프린터 큐 풀이

1. 문제

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

1966번: 프린터 큐

 

2. 풀이

백준에서 시뮬레이션과 큐 알고리즘으로 분류되어 있는 문제이다. 처음 이 문제를 보았을 때 예제 입력을 제대로 보지 않고 우선순위 큐(PriorityQueue)를 이용하면 한번에 해결될 거 같다고 생각해서 그냥 바로 코드를 작성했다가 1 1 9 1 1 1 입력을 보고 다시 코드를 수정했다. 문제를 제대로 읽어야 한다는 것을 다시 한번 느끼게 해주었다.

이 문제는 단순히 값으로 비교하는 것이 아니라 인덱스와 그 인덱스의 배열 값, 두 가지를 모두 생각해야 하는 문제이다. 먼저 입력값을 받은 후 Queue를 선언할 때 자료형을 인덱스와 배열 값 두 가지를 받을 수 있게 정수형 배열로 잡았다. (이것을 생각하지 못해서 한참을 고민하고 다른 분의 풀이를 참고하였다.)

문제에서 현재 문서보다 중요도가 높은 문서가 하나라도 있다면 인쇄하지 않고 큐의 맨 뒤로 배치한다고 한다. 그래서 while 반복문 안에서 큐에 있는 하나의 배열을 꺼내어 반복문을 돌려서 하나라도 큰 값이 있는지를 비교한다. 그 비교 값에 따라 boolean 변수인 flag 값을 셋팅한다. (1) flag가 false라면 문제에서 제시한대로 큐의 맨 뒤로 셋팅하고 (2) flag가 true라는 것은 현재 꺼낸 배열의 값보다 큰 값이 큐 안에 없다는 이야기이므로 그 값을 인쇄하고 결과 값에 +1을 한다. 결과 값에 +1을 한다는 의미는 문제에서 몇 번째로 인쇄되는지를 출력하는지 출력하라고 했기 때문에 그 순서를 더해주는 것이다. 이때 이 값이 입력으로 주어졌던 위치에 있는 배열 값이라면 정답을 인쇄한 것이기에 반복문을 종료한다. 그 값이 아니라면 동일한 값이 큐에 남아있다는 이야기이므로 다시 탐색을 진행한다.(예제 입력 1의 테스트 3번 케이스에 해당 : 1 1 9 1 1 1)

 

3. 소스 코드

package simulation;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        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 st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 문서의 개수
            int M = Integer.parseInt(st.nextToken()); // 궁금한 문서가 queue에 몇 번째에 놓여 있는지
            int result = 0;

            Queue<int[]> queue = new LinkedList<>();

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                int temp = Integer.parseInt(st.nextToken());
                queue.add(new int[] {i, temp});
            }

            while (true) {
                int[] out = queue.remove();
                boolean flag = true;

                for (int[] output : queue) {
                    if (output[1] > out[1]) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    result += 1;
                    if (M == out[0]) {
                        break;
                    }
                }
                else {
                    queue.add(out);
                }
            }

            bw.write(Integer.toString(result) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}