백준 1202 코틀린

처음에 떠오른 방법은 정렬 후 그리디로 풀려고 했지만 시간초과가 나왔다.
시간초과 없이 해결하기 위해서는 트리 구조와 같은 우선순위 큐나 객체 참조 해쉬등을 이용하여 풀어야 되는 걸 알았지만
왜 그런지 오기가 생겨 처음 방법으로 계속 풀다가 계속 실패하고 결국 우선순위 큐를 이용하였다 ㅠ

 

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

 

 

보석과 가방을 무게순으로 정렬한 다음

각 가방의 무게보다 같거나 작은 배낭을 value값 기준의 우선순위 큐에 넣어주고

이중 가장 값어치가 높은 보석을 꺼내 sum에 더해 준다.(가방에는 한개의 보석만 가능함으로)

그리고 우선순위 큐에 남아있는 보석들은 (가방을 무게순으로 정렬했기 때문에 다음 가방에 넣을 수 있는) 다음 추가되는 보석들과 같이 우선순위큐에 남아 있게 된다.

 

import java.util.*
import kotlin.Comparator
import kotlin.collections.ArrayList

fun main() {
    val firstInput = readLine()!!.split(" ")
    val n = firstInput[0].toInt()
    val k = firstInput[1].toInt()
    val jewelries = ArrayList<Jewelry>()
    val bags = ArrayList<Int>()
    val pq = PriorityQueue(Comparator.reverseOrder<Int>())
    var sum: Long = 0
    var position = 0

    for (i in 0 until n) {
        val info = readLine()!!.split(" ")
        jewelries.add(Jewelry(info[0].toInt(), info[1].toInt()))
    }

    for (i in 0 until k) {
        bags.add(readLine()!!.toInt())
    }

    jewelries.sortWith(Comparator<Jewelry> { j1, j2 ->
        if (j1.weight == j2.weight) {
            j2.value - j1.value
        } else j1.weight - j2.weight
    })

    bags.sort()

    for(bag in bags) {

        for (i in position until jewelries.size) {
            if (jewelries[i].weight <= bag) {
                pq.offer(jewelries[i].value)
                position = i + 1
            } else {
                break
            }
        }

        if (!pq.isEmpty()) {
            sum += pq.poll()
        }
    }
    println(sum)
}

data class Jewelry(
    val weight: Int,
    val value: Int
)