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

 

🔒 문제

 

 

🧠 아이디어

문제 제목처럼 최소힙, 최대힙의 우선순위 큐 2개를 운영하는 방식을 떠올릴 수 있고 매우 직관적이다.

힙은 중복 데이터를 허용하므로 ㅎㅎ;;

 

 

중복원소를 허용하는 방식으로 탐색까지 $$ 모두 O(Log N) $$ 으로 만들 수 있는 방법이 있다.

바로 TreeMap<Int,Int> 를 사용하는 것이다.

 

또, 굉장히 효자 API 를 제공한다. 우선순위 큐가 root 만 추출하기 편했다면

이 문제에서 요구하는 것 처럼 하나의 데이터셋 안에서 우선순위가 가장 높은 / 낮은 값을 추출할 수 있다.

 

TreeMap, TreeSet 은
Binary Search Tree 로 구현되어 있으므로
모든 연산이 O(Log N) 이다.

 

근데 firstEntry(), firstKey() 이런거 시간복잡도 O(Log N) 맞아?

맞다. BST 의 왼/오른으로 이동하여 트리의 높이인 O(Log N) 의 시간이 소요된다.

 

🔑 Kotlin Code

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

private val MAX = 1
private val MIN = -1

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

    repeat(numOfTC){
        val numOfOperation = br.readLine().toInt()
        // 오름차순
        val treeMap = TreeMap<Int,Int>(){key1, key2-> key1.compareTo(key2)}

        for(i in 1 .. numOfOperation){
            val str = br.readLine().split(" ")
            val op = str.first()
            val num = str.last().toInt()

            when (op) {
                "I" -> {
                    if(treeMap.containsKey(num)) {
                        treeMap[num] = treeMap[num]!!.plus(1)
                    } else {
                        treeMap[num] = 1
                    }
                }
                "D" -> {
                    if (treeMap.isEmpty()) continue
                    when (num) {
                        MAX -> {
                            val (num, cnt) = treeMap.lastEntry()
                            if (cnt == 1) treeMap.remove(num)
                            else treeMap[num] = (cnt - 1)
                        }
                        MIN -> {
                            val (num, cnt) = treeMap.firstEntry()
                            // unique value
                            if (cnt == 1) treeMap.remove(num)
                            else treeMap[num] = (cnt - 1)
                        }
                    }
                }
            }
        }

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

    print(sb)
}