[백준, 1966번] 프린터 큐 (Queue 큐, PriorityQueue 우선순위 큐, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

이번 "백준 - 프린터 큐" 문제를 요약한다면 다음과 같습니다.

 

• 문서들이 큐에 순서대로 들어가 있고, 각 문서는 중요도를 가집니다.
• 큐에서 문서를 인쇄할 때, 현재 문서보다 중요도가 높은 문서가 뒤에 있으면 현재 문서를 큐의 맨 뒤로 보냅니다.
• 특정 문서가 몇 번째로 인쇄되는지 구해야 합니다.

 

큐만을 이용해서 구할 수 도 있지만 중요도가 있는 만큼 우선순위 큐를 사용하면 효율적으로 풀이할 수 있습니다.

[자료구조 JAVA] 우선순위 큐(Priority Queue) 클래스 알아보기 ✔

---

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

 

우선순위 큐는 일반적으로 우선순위 큐는 작은 값이 더 높은 우선순위를 가지지만 위와 같이 정렬을 변환한다면 큰값이 더 높은 우선순위를 가질 수 있습니다.

---

우선순위 큐를 구현하는 단계는 다음과 같이 처리했습니다.

 

• 문서의 중요도를 저장하는 PriorityQueue를 준비합니다. (내림차순으로 정렬)
• 큐에는 (문서 인덱스, 중요도)를 저장하고, 우선순위 큐에는 문서의 중요도만 저장합니다.
• 큐에서 문서를 꺼내고, 우선순위 큐의 최고 중요도와 비교합니다.
  • 중요도가 같다면 문서를 출력합니다.
  • 중요도가 다르다면 문서를 큐의 맨 뒤로 보냅니다.
• 목표 문서가 출력될 때까지 반복합니다.

 

---

전체 코드

 

먼저, 빠른 입력 처리를 위해 BufferedReader 클래스를 사용하여 입력을 받습니다. 입력된 값은 공백을 기준으로 토큰을 분리하기 위해 StringTokenizer를 사용합니다.

 

일반 큐는 [인덱스, 중요도] 형식으로 저장되므로, 배열 타입으로 초기화합니다. 반면, 우선순위 큐는 reverseOrder를 사용하여 중요도가 높은 순서대로 내림차순 정렬됩니다.

 

문서의 개수(N)만큼 반복하여 큐와 우선순위 큐를 채워주고, M번째로 출력되는 문서를 추적하기 위해 출력 순서를 기록할 변수 printCount를 초기화합니다.

 

그 후 poll() 메서드를 사용하여 큐에서 문서를 꺼내고, 이를 current_queue에 저장합니다. peek() 메서드를 이용해 우선순위 큐에서 가장 높은 중요도를 가진 문서를 확인하고, 현재 문서의 중요도와 비교합니다. 만약 두 중요도가 같다면, 해당 문서는 출력 가능한 문서이므로 출력 카운트(printCount)를 증가시킵니다.

 

이 과정에서, 만약 현재 문서의 인덱스가 M과 같다면 그 문서가 출력된 순서를 출력하고, 만약 가장 높은 중요도를 가진 문서가 아니라면 해당 문서를 큐의 맨 뒤로 다시 삽입합니다.

---

 

글로 설명하기보다는 그림으로 보는 것이 더 이해하기 쉬울 것 같아 그림을 준비했습니다.