[백준/코틀린] 7662번: 이중 우선순위 큐

링크

7662번: 이중 우선순위 큐

개요

최솟값과 최댓값을 모두 반환할 수 있는 이중 우선순위 큐를 두 가지 방식으로 구현합니다.

• 풀이 1: PriorityQueue
• 풀이 2: TreeMap

풀이 1: PriorityQueue

두개의 PriorityQueue를 이용한 Lazy Deletion 방식으로 이중 우선순위 큐를 구현합니다.

최솟값 큐(minQ)와 최댓값 큐(maxQ)를 모두 유지하며,
삭제된 원소는 바로 제거하지 않고 삭제 여부만 기록해 두는 Lazy Deletion 방식으로 두 큐의 상태를 동기화합니다.

[WIKIPEDIA] Lazy Deletion

코드

import java.util.*

data class Entry(
    val index: Int,
    val value: Int,
)

fun PriorityQueue<Entry>.poll(deleted: BooleanArray): Entry? {
    while (isNotEmpty() && deleted[peek().index]) poll()

    return poll()
}

fun main() = repeat(readln().toInt()) {
    val k = readln().toInt()
    val minQ = PriorityQueue<Entry>(compareBy { it.value })
    val maxQ = PriorityQueue<Entry>(compareByDescending { it.value })
    val deleted = BooleanArray(k)

    repeat(k) { index ->
        val (op, x) = readln().split(" ").let { it[0] to it[1].toInt() }

        when (op) {
            "I" -> {
                minQ.add(Entry(index, x))
                maxQ.add(Entry(index, x))
            }

            "D" -> {
                val pq = if (x > 0) maxQ else minQ

                pq.poll(deleted)?.also { deleted[it.index] = true }
            }
        }
    }

    val min = minQ.poll(deleted)
    val max = maxQ.poll(deleted)

    println(
        if (min == null || max == null) "EMPTY"
        else "${max.value} ${min.value}"
    )
}

풀이 2: TreeMap

TreeMap을 멀티셋(Multiset)처럼 활용하는 방식으로 이중 우선순위 큐를 구현합니다.

key가 정렬된 상태로 유지되기 때문에,
각 값의 등장 횟수를 저장해 멀티셋(Multiset)처럼 활용할 수 있습니다.

코드

import java.util.*

fun main() = repeat(readln().toInt()) {
    val treeMap = TreeMap<Int, Int>()

    repeat(readln().toInt()) {
        val (op, x) = readln().split(" ").let { it[0] to it[1].toInt() }

        when (op) {
            "I" -> treeMap[x] = treeMap.getOrDefault(x, 0) + 1
            "D" -> if (treeMap.isNotEmpty()) {
                val key = if (x > 0) treeMap.lastKey() else treeMap.firstKey()

                treeMap.computeIfPresent(key) { _, cnt -> (cnt - 1).takeIf { it > 0 } }
            }
        }
    }

    println(
        if (treeMap.isEmpty()) "EMPTY"
        else "${treeMap.lastKey()} ${treeMap.firstKey()}"
    )
}