[Kotlin] 백준 7662 : 이중 우선순위 큐

문제 링크

7662번: 이중 우선순위 큐

---

---

문제 해설

처음에는 최대힙과 최소힙을 하나씩 만들어서 구현하려고 했는데 시간 초과가 났다. 제거 연산을 수행할 때 'D 1'이면 최대힙에서 제거한 값을 최소힙에서 remove()로 제거하고, 'D -1'이면 최소힙에서 제거한 값을 최대힙에서 같은 방법으로 제거하는 방식으로 구현했는데 저 remove() 과정에서 힙을 탐색해야 하다보니 시간을 초과한 것 같아서 다른 방법을 찾아보기로 했다.

 

그런 이유로 TreeMap을 이용하여 문제를 풀어보았는데 성공적으로 해결했다. TreeMap은 key를 정렬해서 저장하는 Map 구조로, key에 삽입 연산으로 들어오는 값을, value에 해당 key가 삽입된 횟수를 저장한다. key의 최대값이나 최소값의 value가 1인 상태에서 제거 연산을 해야 할 때는 value를 줄이는 게 아니라 Map에서 key를 제거한다. 모든 연산을 끝냈을 때 Map의 마지막 key가 최대값이 되고 첫 번째 key가 최소값이 된다.

---

Code

import java.util.StringTokenizer
import java.util.TreeMap

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    var st: StringTokenizer
    var n: Long
    repeat(readLine().toInt()) {
        val tm = TreeMap<Long, Int>()
        repeat(readLine().toInt()) {
            st = StringTokenizer(readLine())
            when (st.nextToken(" ")) {
                "I" -> tm[st.nextToken(" ").toLong().also { n = it }] = tm.getOrDefault(n, 0) + 1
                "D" -> {
                    if (tm.isNotEmpty()) {
                        val key = if (st.nextToken() == "1") tm.lastKey() else tm.firstKey()
                        if (tm[key] == 1) tm.remove(key)
                        else tm[key] = tm[key]!! - 1
                    }
                }
            }
        }

        sb.append("${if (tm.isEmpty()) "EMPTY" else "${tm.lastKey()} ${tm.firstKey()}"}\n")
    }
    println(sb)
}