[백준(JAVA)] 1966번: 프린터 큐

문제

✔ 난이도 - Silver 3

설명

N개 문서의 중요도와 궁금한 문서가 몇 번째에 놓여있는지 즉, 궁금한 문서의 idx번호가 주어진다.
각 문서의 idx와 중요도를 함께 알고 있어야 하기 때문에 int[] 배열을 써서
1. idx와 2. 중요도
이 두 가지를 함께 관리한다.

Queue<int[]> queue = new LinkedList<>();
이렇게 큐를 선언하고
queue.add(new int[] {idx, priority});
idx와 중요도를 함께 배열로 큐에 삽입해준다.

현재 큐의 맨 앞 문서의 중요도가 가장 높은 중요도인지 판단을 위해 주어진 N개 문서의 중요도들을 내림차순으로 정렬할 필요가 있다. 이 때 우선순위큐를 사용하여 정렬해준다.
https://velog.io/@seha01130/JAVA-우선순위-큐Priority-Queue
그럼 우선순위큐에서 peek()한 수 즉, 현재 남아있는 문서들 중 가장 높은 중요도와 현재 큐의 맨 앞 문서의 중요도가 일치하는지 비교를 통해 문제를 해결할 수 있다.

풀이

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int testCase = 0; testCase < T; testCase++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); //문서의 갯수
            int M = Integer.parseInt(st.nextToken()); //궁금한 문서의 현재 순서

            Queue<int[]> queue = new LinkedList<>();
            PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < N; i++){
                int idx = i;
                int priority = Integer.parseInt(st.nextToken());
                queue.add(new int[] {idx, priority});
                pQueue.add(priority);
            }
            // 큐에 인덱스/중요도 삽입, 우선순위큐에 중요도 삽입 완료

            int count = 0;
            while (!queue.isEmpty()){
                int[] current = queue.poll();
                int idx = current[0];
                int priority = current[1];

                if (priority == pQueue.peek()){
                    pQueue.poll();
                    count++;
                    if (idx == M){
                        break;
                    }
                } else {
                    queue.add(current);
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }
}

⏰ 시간복잡도

우선 하나의 테스트케이스의 시간복잡도를 구해보자.
for문 : O(N)
while문 : 최악의 경우 O(N²)

• queue.poll() : O(1)
• pQueue.peek() : O(1)
• pQueue.poll() : O(logN)
• queue.add(current) : O(1)

그러나 while문의 시간복잡도는 최악의 경우 O(N²)이 될 수 있다.
queue.add(current) 부분에서 앞쪽 문서가 계속 뒤로 밀려나며, 모든 문서가 여러 번 다시 큐에 삽입될 수 있기 때문이다.
즉, 문서가 N개고, 각 문서가 최악의 경우 N번 다시 뒤로 밀릴 수 있다면
N개의 문서 × N번의 재배치 -> O(N²)

따라서 전체 시간복잡도는 O(T × N²) 가 된다.

TIL💡

📌 Priority Queue
https://velog.io/@seha01130/JAVA-우선순위-큐Priority-Queue

📌 Queue에 배열 저장하기

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

// 큐에 [문서 인덱스, 중요도] 배열 형태로 저장
queue.add(new int[] {idx, priority});