문제 풀이/백준

[백준] 1966번. 프린터 큐(Kotlin)

27200 2025. 10. 14. 17:00

문제

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


풀이(18분)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()

    var st: StringTokenizer

    var T = br.readLine().toInt()
    while (T-- > 0) {
        st = StringTokenizer(br.readLine())
        val N = st.nextToken().toInt()
        val num = st.nextToken().toInt()
        val pq = PriorityQueue<Node>()
        val q = LinkedList<Node>()
        st = StringTokenizer(br.readLine())
        for (i in 1..N) {
            val temp = st.nextToken().toInt()
            var n = Node(false, temp)
            if (i - 1 == num) {
                n.flag = true
            }
            pq.add(n)
            q.add(n)
        }

        var max = pq.poll()
        var cnt = 0
        while (true) {
            var temp = q.poll()
            if (temp.priority == max.priority) {
                cnt++
                max = pq.poll()
                if (temp.flag) {
                    sb.append(cnt).append("\n")
                    break
                }
            } else {
                q.add(temp)
            }
        }
    }
    println(sb)
}

class Node(
    var flag: Boolean,
    val priority: Int
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return other.priority - this.priority
    }
}

문제 풀이 전략

우선순위 큐를 사용해 현재 최고 우선순위를 빠르게 찾고,
큐에서 문서를 하나씩 꺼내며 해당 우선순위와 일치할 때 출력 순서를 증가시켰다.
특정 문서를 추적하기 위해 flag가 포함된 Node 클래스를 사용했다.