[Java] 백준 1966번: 프린터 큐

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

 

 

문제 분석

• 프린터의 대기열이 존재한다고 할 때, 대기열의 문서들은 중요도를 나타내는 정수로 나타낸다. 예) 1 6 2 9
• 각 정수를 Queue에 담고, 문서(중요도)를 하나씩 뽑아서 남아 있는 문서들의 중요도와 비교한다. 
  • 정수가 클수록 높은 중요도를 나타내며, 먼저 출력된다.
  • 중요도에 따라 Queue에 담긴 문서들의 위치들이 바뀌므로 배열의 형태로 인덱스와 함께 저장해야 한다.
  • 원하는 문서가 몇 번째로 출력되는지 출력하기 위해 위치가 바뀔 때마다 별도의 count를 증가시킨다.
  • 현재의 문서가 가장 중요도가 크다면?
    👉 원하는 문서와 인덱스가 일치한지 비교하여 일치한다면 반복문을 벗어난 후 count를 출력한다.
    👉 원하는 문서가 아니라면 while문을 통해 그 다음 문서를 기준으로 하는 반복을 시작한다.
  • 현재의 문서보다 더 큰 중요도를 가진 문서가 존재한다면?
    👉 Queue에 다시 넣는다.

 

문제 풀이

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

public class BOJ_1966_프린터큐 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스

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

            Queue<Integer[]> q = new LinkedList<>(); // 프린터 대기열 { 인덱스, 문서(중요도) }

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); // 문서의 개수
            int M = Integer.parseInt(st.nextToken()); // Queue에서의 위치

            // 문서(중요도)를 프린터 대기열에 넣는다
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++)
                q.add(new Integer[]{ j, Integer.valueOf(st.nextToken()) });

            int count = 0; // 몇 번째로 인쇄되는지 카운트
            while (true) {

                Integer[] now = q.poll();
                boolean max = true; // 현재 문서(now)보다 더 중요도가 큰 문서가 있는지 판별

                for (Integer[] integers : q) {

                    // 현재 문서의 중요도보다 더 큰 중요도가 있다면 max를 false로 바꾸고 벗어난다
                    if (integers[1] > now[1]) {
                        max = false;
                        break;
                    }
                }

                // max가 true이면
                if (max) {
                    // count를 증가시키고
                    count++;
                    // 몇 번째로 인쇄되었는지 궁금한 문서라면 while문을 벗어난다
                    if (M == now[0]) break;
                } else {
                    // max가 false이면 중요도가 나중이므로 q의 뒤에 넣는다
                    q.add(now);
                }
            }

            System.out.println(count);
        }
    }
}