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

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

7662번: 이중 우선순위 큐

 

 

난이도 : 골드 4
태그 : 자료구조, 트리를 사용한 집합과 맵, 우선순위 큐

 

 

설명

우선순위가 최대 혹은 최소인 원소만 뺏던 기존 우선순위 큐와 달리,

최대와 최소 모두 뺄 수 있는 우선순위 큐 입니다.

 

LinkedList도 써보고, 직접 배열로 우선순위 큐도 구현해 봤는데...

시간초과에서 헤어나오질 못해 검색해 봤더니 TreeMap이라는 자료구조를 발견하게 되었습니다.

 

TreeMap은 키값이 하나 들어올 때마다 정렬되기 때문에 더 효율적으로 동작합니다.

 

 

 

 

소스코드

TreeMap 생성

val treeMap = TreeMap<Int, Int>()

먼저, 해당 문제에서 쓸 treeMap을 선언합니다.

 

I 연산

if (input[0] == "I") {
    treeMap[input[1].toInt()] = treeMap.getOrDefault(input[1].toInt(), 0) + 1
}

TreeMap의 getOrDefault(key, defualtValue)는 key값을 넘겨주어 해당 키가 있으면 값을 받고,

없으면 DefaultValue로 건네준 인자를 반환하는 메소드 입니다.

 

해당 키 값이 있으면 1만큼 증가시켜 주고,

해당 키 값이 없다면 1로 키와 함께 treeMap에 넣습니다.

 

D 연산

else {
    if (treeMap.size == 0) continue
    // D
    val key = if (input[1] == "1") treeMap.lastKey() else treeMap.firstKey()
    val keyCnt = treeMap[key]
    if (keyCnt == 1) treeMap.remove(key)
    else treeMap[key] = keyCnt!! - 1
}

 

 

 

D 1은 최대 우선순위를, D -1는 최소 우선순위를 제거하는 연산입니다.

 

다만, treeMap에 원소가 없다면 D연산을 진행할 수 없으므로 continue를 통해 다음 케이스로 넘어갑니다.

 

D 1 연산의 경우 treeMap의 LastKey를, D -1 연산의 경우 treeMap의 FirstKey를 가져와 해당 키와 키값을 얻습니다.

키값이 1인 경우(같은 우선순위가 1개인 경우), 해당 원소를 큐(treeMap)에서 꺼내면 되겠죠?

만약 키값이 2개 이상인 경우(같은 우선순위가 여러개 있을 경우) 해당 원소를 1개만큼 줄이면 됩니다.

 

 

if (treeMap.size == 0)
    println("EMPTY")
else
    println("${treeMap.lastKey()} ${treeMap.firstKey()}")

이후 treeMap의 사이즈가 0이라면 EMPTY를,

비어있지 않다면 마지막값 (우선순위 최대)과 첫번째값(우선순위 최소)를 출력합니다.

 

 

전체 소스코드

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

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

    repeat(T) {
        val n = br.readLine().toInt()
        val treeMap = TreeMap<Int, Int>()

        for (i in 0 until n) {
            val input = br.readLine()!!.split(" ")

            if (input[0] == "I") {
                treeMap[input[1].toInt()] = treeMap.getOrDefault(input[1].toInt(), 0) + 1
            } else {
                if (treeMap.size == 0) continue
                // D
                val key = if (input[1] == "1") treeMap.lastKey() else treeMap.firstKey()
                val keyCnt = treeMap[key]
                if (keyCnt == 1) treeMap.remove(key)
                else treeMap[key] = keyCnt!! - 1
            }
        }

        if (treeMap.size == 0)
            println("EMPTY")
        else
            println("${treeMap.lastKey()} ${treeMap.firstKey()}")
    }
}

 

 

후기

단순하게 머리속에 떠오르는 방법으로 풀이했더니 시간초과의 늪에 빠진 문제였습니다.

 

도저히 방법이 생각나지 않아 구글링을 해봤더니, TreeMap이라는 자료구조를 찾아 풀이하였습니다.

 

자바(코틀린)에는 제가 모르는 자료구조가 아직 많은 것 같네요. 더 공부 해야겠습니다.