1966번: 프린터 큐 [JAVA]

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

 

접근 방식)

Queue에 다 넣어서 빼고 뒤에 넣고 하려고 했더니, 

"나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다."

그래서 프린터 대기열을 위한 일반 Queue와 우선순위 확인을 위한 PriorityQueue를 함께 사용하려고 한다..!

그리고 편의를 위해 문서Document 클래스를 만들었다. 문서 순서(order)와 우선순위(priority)를 속성으로 가진다.

 

1. 테스트케이스 T만큼 반복문 수행

2. 중요도는 내림차순이므로, 우선순위큐 정렬 기준을 재정의해줬다.

3. 문서의 개수만큼 반복문 돌면서 일반Queue와 우선순위큐pq에 값 넣어준다.

4. 일반Queue의 문서가 없을 때까지 반복문 수행

4-1) 일반Queue에서 하나씩 빼서 우선순위큐의 첫번째 문서와 우선순위와 같은지 확인한다.

     우선순위가 같다면, 

     4-1-1) 일반Queue에서 뺀 문서의 순서와 우리가 확인하고자 하는 문서 순서(checkNum)이 같은지 확인 후,

     같으면 StringBuilder에 append() 해주고 반복문 break; → 나중에 출력해주기 위해서

     4-1-2) 우선순위가 같으니 우선순위큐pq에서 출력(pq.poll)하고 출력횟수 count++

4-2) 일반Queue 문서의 우선순위 != 우선순위큐pq 문서의 우선순위

일반Queue 문서 뺀거 맨 뒤에 다시 넣어준다.

 

package tony_git.data_structure;

import java.io.*;
import java.util.*;
public class B_1966 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int k = 0; k < T; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            Queue<Document> queue = new LinkedList<>();
            PriorityQueue<Document> pq = new PriorityQueue<>((d1, d2) -> {
                return d2.priority - d1.priority;
            });

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

            // document의 order와 M이 같은 걸 찾으면 된다.
            int count = 1;
            while (!queue.isEmpty()) {
                Document now = queue.poll();
                if (now.priority == pq.peek().priority) {
                    if (now.order == M) {
                        sb.append(count).append('\n');
                        break;
                    }
                    pq.poll();
                    count++;
                } else {
                    queue.add(now);
                }
            }
        }
        System.out.print(sb);
    }
}

class Document {
    int order;
    int priority;

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