[백준] 1202 - 보석 도둑

Priority Queue (우선순위 큐) 및 배열을 이용하여 푸는 문제이다.
보석의 무게와 가격은 최소힙, 최대힙으로, 배열 및 정렬을 이용하여 가방의 무게를 저장하고 이를 순회하며 해당하는 값들만 출력하면 된다.

풀이

data class Jewel(val weight: Int, val price: Long)

fun `1202-보석 도둑`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, k) = br.readLine().split(" ").map{ it.toInt() }
    // 무게가 작은 보석을 우선으로 한다
    val jewelHeap = PriorityQueue<Jewel>(compareBy { it.weight })
    var sum = 0L

    repeat(n){
        val token = StringTokenizer(br.readLine())
        val weight = token.nextToken().toInt()
        val price = token.nextToken().toLong()

        jewelHeap.offer(Jewel(weight, price))
    }

    // 가방 무게 오름차 순
    val bagArr = IntArray(k){ br.readLine().toInt() }.apply { sort() }

    // 같은 무게에서 가격 내림차 순 설정하기 위해 등록
    val priceJewelHeap = PriorityQueue<Jewel>(compareByDescending { it.price })

    /*
    * 적재 무게가 작은 가방부터 순회하며, 최소 힙인 보석을 꺼낸 후 저장한다.
    * 저장하는 PriorityQueue 는 가격 순인 최대힙이므로 큰 가격이 우선된다.
    * 
    * 다음 진행 시에도 반복하며 진행한다.
    * */
    for(bag in bagArr){
        while (jewelHeap.isNotEmpty() && jewelHeap.peek().weight <= bag){
            priceJewelHeap.offer(jewelHeap.poll())
        }

        if(priceJewelHeap.isNotEmpty()){
            sum += priceJewelHeap.poll().price
        }
    }

    bw.write(sum.toString())
    bw.flush()
    bw.close()
    br.close()
}

시간을 조금 더 줄이고 싶다면 data class 구현이 아닌 Pair 로 진행할 수 있다.

후기

정답 비율이 23% 였던 것 치고는 생각보다 어렵지 않았다.
다만, 처음에는 정렬 순서를 어떻게 할지 조금 헷갈렸고 data class 에 Comparable 인터페이스를 따로 구현할까 고민도 여럿 했었으나, 서로 다른 조건의 PriorityQueue 를 사용해야했기에 불필요한 과정이라 생각되어 폐기하였다.

의외로 쉽게 풀려서 놀란 문제.