/<BOJ 백준 1966번> 프린터 큐 - Java

문제 1966번 : 프린터 큐

문제 해설

문제의 이름과 설명에 나와있듯이 자료구조 큐(Queue)를 이용하여 문제를 풀 수 있다. 큐의 선입선출(First-In-First-Out) 특성을 이용하면 어렵지 않게 풀 수 있는 문제이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        Queue<int[]> queue = new LinkedList<>(); // 큐에 (인덱스, 우선순위) 쌍으로 저장

        for (int i = 0; i < testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

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

            int count = 0;

            while (!queue.isEmpty()) {
                int[] front = queue.poll();
                int index = front[0];
                int priority = front[1];

                boolean isHighestPriority = true;

                // 큐에 남아있는 원소들 중에 현재 문서보다 우선순위가 높은 문서가 있는지 확인
                for (int[] document : queue) {
                    if (document[1] > priority) {
                        isHighestPriority = false;
                        break;
                    }
                }

                if (isHighestPriority) {
                    count++;
                    if (index == M) {
                        System.out.println(count);
                        break;
                    }
                } else {
                    // 우선순위가 높은 문서가 있으면 다시 큐의 뒤로 이동
                    queue.add(new int[] { index, priority });
                }
            }

            queue.clear(); // 큐를 비워 다음 테스트 케이스를 위해 초기화
        }
    }

    public static void main(String[] args) throws Exception {
    	new Main().solution();
    }
}

 

큐에 정수형 배열을 하나의 원소로 추가하였다. 배열은 각각 {인덱스, 우선순위} 로 구성되어 있다. 입력에서 O(testCase * N) 시간복잡도를 갖으므로 전체 코드는 O(N*N)의 시간복잡도를 갖는다.