백준 1966번 | 프린터큐 문제 풀이 (Java)

문제

 

제출코드

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

public 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) {
            String[] command = br.readLine().split(" ");

            // 문서 개수
            int N = Integer.parseInt(command[0]);

            // 찾고 싶은 문서 위치
            int M = Integer.parseInt(command[1]);

            Deque<Document> queue = new ArrayDeque<>();

            // 중요도 내림차순
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

            String[] arr = br.readLine().split(" ");
            for(int i = 0; i < N; i++) {
                int priority = Integer.parseInt(arr[i]);
                queue.add(new Document(priority, i ));
                priorityQueue.add(priority);
            }

            // 인쇄 순서
            int count = 0;
            while(!queue.isEmpty()) {
                // 맨 앞 문서 꺼내기
                Document current = queue.poll();

                if(current.priority == priorityQueue.peek()) {
                    // 가장 높은 중요도의 문서라면 인쇄
                    priorityQueue.poll();
                    count++;

                    if(current.index == M) {
                        bw.append(count+"\n");
                        break;
                    }
                } else {
                    // 중요도가 높은 문서가 남아 있다면 다시 큐에 넣음
                    queue.add(current);
                }
            }
        }

        br.close();
        bw.flush();
        bw.close();


    }

    static class Document {
        int priority;
        int index;

        Document(int priority, int index) {
            this.priority = priority;
            this.index = index;
        }
    }
}

 

Document 클래스 생성

- priority : 중요도

- index : 원래 위치

 

문서 저장할 Deque 생성

중요도 내림차순 저장할 PriorityQueue 생성

 

맨 앞 문서 꺼내서 중요도가 높은 것인지 조건 비교

중요도가 높은 문서일 경우 PriorityQueue에서 꺼내고 카운팅

현재 찾고 있는 문서 일경우 출력 후 탈출

 

중요도가 높지 않은 문서인 경우

다시 맨 뒤에 넣기

 

 

 

 

문제 의도

- 큐의 기본 동작 이해

 

문제 출처