백준 7662 이중 우선순위 큐 (kotlin)

문제 자체는 이해하기 쉽다. 우리가 알고 있는 우선순위 큐의 삽입 연산은 동일하고, 삭제 연산만 양쪽 방향으로 모두 가능하게 하고 싶다는 것이다.

첫번째 풀이

큐를 양방향으로 두 개를 생성,각 원소가 존재해야 하는 갯수를 추적하는 해시맵 생성.
삽입은 항상 두 큐 모두 같이 해주고, 삭제시에는 한쪽을 기준으로 삭제한다. 여기서 문제는 한쪽큐의 삭제를 다른쪽 큐에서는 알 수 없다는 것이다.
이를 위해 삭제할때 해시맵을 토대로 이게 있는게 맞는지 검사하고 없다면 다시 삭제연산을 호출하며 이걸 반복.

결과

생각보다 좀 시간복잡도가 크다고 판단하고 다른 사람들의 풀이와 블로그를 찾아보다가 TreeMap으로 풀면 더 쉽다는 것을 발견. 트리맵을 써본 적이 없어서 찾아보니, 다음과 같은 특징이 있었다.

Map이다. 그런데, 키들이 이진트리 구조로 오름차순으로 정렬된다. 이진트리 구조라는 특징 덕분에 순서를 유지하면서 삽입, 삭제를 해도 logN의 시간. put연산(삽입 혹은 갱신)과 remove연산(제거)을 활용.
put의 경우 value를 갱신하는 함수이며 반환값은 oldValue임.

이를 통해 구현해보니, 다음과 같이 코드가 짧아지고 시간도 줄어들었다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.TreeMap

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(br.readLine().toInt()) {
        val treeMap = TreeMap<Int, Int>()
        repeat(br.readLine().toInt()) {
            val input = br.readLine().split(" ")
            val op = input[0]
            val n = input[1].toInt()
            if (op == "I") {
                treeMap.put(n, treeMap.getOrDefault(n, 0) + 1)
            } else {
                if (treeMap.isEmpty()) return@repeat
                val key = if (n == 1) {
                    treeMap.lastKey()
                } else {
                    treeMap.firstKey()
                }
                if (treeMap.put(key, treeMap.getOrDefault(key, 0) - 1) == 1) {
                    treeMap.remove(key)
                }
            }
        }
        if (treeMap.isEmpty()) {
            println("EMPTY")
        } else {
            println("${treeMap.lastKey()} ${treeMap.firstKey()}")
        }
    }
}

양방향 큐와 트리맵 모두 다 풀이가 가능하나 확실히 트리맵이 간단해서 좋았다. 생각보다 유용히 쓰일 것 같은 컬렉션 클래스인듯하다.