[백준] 1966. 프린터 큐 (Java) [Queue + PrioirtyQueue]

문제

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

1966번: 프린터 큐

 

 

사용한 알고리즘

큐(Queue) + 우선순위 큐(PriorityQueue)

 

 

풀이

큐(Queue)에 중요도(int)와 궁금한 문서인지 flag(boolean)을 저장하고,

우선순위큐(PriorityQueue)에 가장 높은 중요도를 저장하였다.

그런다음 큐에서 하나씩 아이템을 빼서 우선순위 큐에서  뺀 가장 높은 중요도 비교하여 문제를 풀었다.

 

자세한건 코드를 확인해보자.

 

코드

import java.util.*;

public class Main {
    static int t = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();

        while (t > 0) {
            t--;
            int N, M;
            N = sc.nextInt();
            M = sc.nextInt();
            Queue<Pair> q = new LinkedList<Pair>();
            PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

            //입력
            for(int i=0; i<N; i++){
                int itemPriority= sc.nextInt(); //각 문서의 중요도
                boolean isCurious = false; //궁금한 문서 표시 flag
                if(i==M){
                    isCurious =true;
                }
                q.add(new Pair(itemPriority, isCurious)); //queue에 저장
                pq.add(itemPriority);
            }

            int answer=0;
            //검사
            while(!q.isEmpty()){
                Pair item =q.peek();
                int highPriority =  pq.peek();

                //큐에서 뺀게 중요도가 가장 높은 아이템이라면
                if(item.priority == highPriority){
                    pq.remove();
                    q.remove();
                    answer++;
                    if(item.flag){ // 궁금한 문서라면 출력
                        System.out.println(answer);
                        break;
                    }
                }
                //큐에서 뺀게 중요도가 가장 높은 아이템이 아니라면
                else{
                    q.remove();
                    q.add(item);
                }
            }
        }
    }

    static class Pair{
        int priority;
        boolean flag;

        public Pair(int priority, boolean flag) {
            this.priority = priority;
            this.flag = flag;
        }
    }
}

 

필자는 PriorityQueue와 Queue를 이용해서 풀었지만,

순수하게 Queue를 이용한 풀이도 있는 것 같다.

https://st-lab.tistory.com/201

 

 

Queue 개념

https://coding-factory.tistory.com/602

[Java] 자바 Queue 클래스 사용법 & 예제 총정리

PriorityQueue 개념

https://coding-factory.tistory.com/603

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리