[Kotlin] 백준 22252 : 정보 상인 호석

문제 링크

22252번: 정보 상인 호석

---

문제 해설

HashMap과 우선순위 큐를 사용하면 문제를 수월하게 해결할 수 있다. HashMap의 Key에 정보 고릴라의 이름을, Value에 정보 고릴라가 가진 정보들의 가치가 내림차순으로 정렬된 우선순위 큐를 저장한다.

 

여기까지 하면 사실상 문제 풀이는 끝난 것이나 다름 없다. 1번 쿼리의 경우에는 Map에 저장되지 않은 정보 고릴라의 이름이 나오면 새로운 우선순위 큐를 생성하여 Map에 저장하고 정보들의 가치를 저장하면 된다. 2번 쿼리의 경우에는 Map에 저장된 우선순위 큐의 크기와 \(b\) 중 더 작은 횟수만큼 해당 고릴라의 우선순위 큐에서 값을 제거하여 정보 가치의 총합에 더하면 된다.

 

\(k\)와 \(C\)가 모두 최대 \(100,000\)이기 때문에 답이 Int 범위를 초과하는 점만 조심하면 된다.

Code

import java.util.PriorityQueue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val gorilla = HashMap<String, PriorityQueue<Int>>()
    var price = 0L
    repeat(readLine().toInt()) {
        StringTokenizer(readLine()).apply {
            when (nextToken()) {
                "1" -> {
                    val name = nextToken()
                    repeat(nextToken().toInt()) {
                        gorilla[name]?.add(nextToken().toInt()) ?: run {
                            gorilla[name] = PriorityQueue<Int>(reverseOrder()).apply { add(nextToken().toInt()) }
                        }
                    }
                }
                "2" -> {
                    val name = nextToken()
                    repeat(minOf(nextToken().toInt(), gorilla[name]?.size ?: 0)) { price += gorilla[name]!!.poll() }
                }
            }
        }
    }
    println(price)
}