[백준 알고리즘] 1966번: 프린터 큐 (JAVA)

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

코드

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

public class prac {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			Queue<Node> q = new ArrayDeque<Node>(); //(우선순위, 인덱스)로 저장
			PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); 
            // (우선순위 내림차순 저장)

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				int p = Integer.parseInt(st.nextToken());
				q.offer(new Node(p, i));
				pq.offer(p);
			}

			int cnt = 0;

			while (!q.isEmpty()) {
				Node cur = q.poll();

				if (cur.priority == pq.peek()) { // 큐에서 뽑은 값이 가장 우선순위가 높음 == 출력 가능
					pq.poll();
					cnt++; // 몇번째로 출력되는지 순서 체크
					if (cur.idx == m) { // 문제에서 주어진 요건에 부합하는지 확인
						sb.append(cnt);
						break;
					}
				}
				q.offer(cur);
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

class Node {
	int priority;
	int idx;
	public Node(int priority, int idx) {
		this.priority = priority;
		this.idx = idx;
	}
}

 

 

풀이

• 문제 자체의 난이도가 그렇게 높지는 않고, 정답률도 꽤나 높습니다. 하지만 해당 문제를 포스팅하는 이유는 간단해 보이는 문제치고는 조금의 생각이 더 필요했다고 느꼈기 때문이고(제 기준), 자주 등장하는 유형이라고 생각했습니다 ! 
• 자료구조를 쓰긴 해야하는데, 어떤 걸 써야할지 꽤 고민했습니다. 하나의 자료구조로 쉽게 해결할 수 있다고 생각했지만 오산이었구요, 큐랑 우선순위 큐를 적절히 활용해야 합니다 !
• 해설은 코드의 주석을 보시면 쉽게 이해하실 거 같습니다 :)