[백준/1966] 프린터 큐 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1966
• 분류 : Queue, PriorityQueue
• 풀이 시간 : 20분

문제 해설

1. 프린터는 먼저 들어온 순서대로 먼저 뽑힘 : 선입선출
2. 작업 진행 중, 뽑으려는 문서의 '중요도'(우선순위) 확인
3. 현재 문서의 중요도보다 높은 중요도를 가진 문서가 있으면 뒤로 보냄
4. 어떤 한 문서가 몇 번째로 인쇄는지?

Solution

풀이 접근 방법

1. 프린터 작업 큐 생성 : 문서 번호와 우선순위 저장 = File Class
2. 문서 뽑을 때 마다 자신보다 높은 우선순위가 뒤에 있는지 반복문으로 확인하면 시간복잡도 매우 증가
   1. 우선순위들만 담은 '우선순위큐' 생성
   2. 중요도가 높은 숫자면 높은 중요도 = 내림차순 우선순위 큐
3. 문서를 뽑을 때 우선순위 큐에서 뽑은 우선순위와 같으면 뽑고, 아니면 뒤로 보냄

정답 코드

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

public class Main {
  static class File {
    int num, priority;

    public File(int num, int priority) {
      this.num = num;
      this.priority = priority;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int T = Integer.valueOf(br.readLine());

    while (T-- > 0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.valueOf(st.nextToken());
      int M = Integer.valueOf(st.nextToken());

      // 현재 프린터 작업 큐
      Queue<File> queue = new LinkedList<File>();
      // 작업들의 우선순위를 담은 우선순위 큐 : 내림차순 정렬
      PriorityQueue<Integer> priority = new PriorityQueue<>(Collections.reverseOrder());

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

        queue.add(new File(i, filePriority));
        priority.add(filePriority);
      }

      bw.write(print(queue, priority, M) + "\n");
    }

    bw.flush();
    bw.close();
  }

  static int print(Queue<File> queue, PriorityQueue<Integer> priority, int targetNum) {
    int count = 1;

    while (!queue.isEmpty()) {
      // 뽑아야 할 문서 가져옴
      File printed = queue.poll();

      // 지금 뽑아야 할 문서의 우선순의 != 작업들의 우선순위의 우선순위큐에서 맨 위
      // 아직 나보다 더 높은 우선순위의 작업물이 뽑히지 않았다
      if (priority.peek() != printed.priority) {
        queue.add(printed);
        continue;
      }

      // 지금 해당 문서를 뽑아야 할 차례
      // 추적하고싶은 문서 번호와 같으면 리턴
      if (printed.num == targetNum) {
        return count;
      }

      // 문서 뽑았으니깐 우선순위도 하나 뽑아서 제거
      priority.poll();
      count++;
    }

    return count;
  }
}