[Kotlin][Algorithm] 1202 - 보석 도둑

문제 요약

보석의 개수와 각 보석의 무게와 가격이 주어질 때 가방 K개에 담을 수 있는 보석의 최대 가격을 구하는 문제

가방에는 1개의 보석만 넣을 수 있음을 주의

문제 접근

문제의 핵심은 주어진 여러 개의 가방 각각에 대해, 가방에 담을 수 있는 무게 한도 내에서 가장 가치가 높은 보석을 선택하여 총 가치를 최대화하는 것입니다

코드를 작성하기전에 생각을 해보면 가장 최대 가격의 경우는 가장 작은 가방 부터 넣을 수 있는 보석 중 최대의 보석을 가져가면 되는 간단한 문제입니다.

전형적인 그리디 문제라고 할 수 있죠

그리디 (Greedy)

가방을 오름차순 정렬 한 후 차례대로 챙길 수 있는 보석 중 가장 높은 보석을 고르면 되므로 직관적으로 생각할 수 있는 방법은
1. 가방 선택
2. 모든 보석을 체크하며 가방에 넣을 수 있는 보석 중 가장 최대가격 보석을 보석 리스트에서 제거
3. 모든 가방에 대해서 1,2 진행

하지만 모든 보석을 매번 체크하며 1,2번을 반복하면 k*n의 시간복잡도가 나오게 됩니다.

이렇게 풀면 시간 초과입니다.(제가 그럼..)

우선순위 큐(Priority Queue)

가방에 담을 수 있는 가장 가치 높은 보석을 효율적으로 찾기 위해 우선순위 큐를 사용합니다. 우선순위 큐는 원소들을 우선순위에 따라 정렬된 상태로 저장하는 자료구조로, 이 문제에서는 보석의 가치를 기준으로 최대 힙(max heap)을 구성하여 가장 가치가 높은 보석을 빠르게 찾을 수 있도록 합니다.

1. 가방을 오름차순 정렬하고 보석 또한 무게순으로 오름차순 정렬합니다.

2. 각 가방을 탐색하며 담을 수 있는 보석만큼 우선순위 큐에 넣어줍니다.

이 때 이전 가방이 탐색한 보석은 다시 볼 필요가 없습니다. 왜냐하면 현재 가방은 이전 가방보다 크기가 크고 이미 이전에 탐색한 보석은 이전 가방에 의해서 우선순위 큐에 들어간 상태이기 때문에 다시 확인할 필요가 없습니다.

따라서 모든 보석을 최대 한번 씩만 탐색하면 되므로
k * NlogN 시간 복잡도로 해당 문제를 해결할 수 있습니다.

코드

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

fun main() {
    val br = System.`in`.bufferedReader()
    val (n, k) = br.readLine().split(' ').map { it.toInt() }
    val jewels = ArrayList<Pair<Int, Int>>(n)
    for (i in 0 until n) {
        val (m, v) = br.readLine().split(' ').map { it.toInt() }
        jewels.add(m to v)
    }
    val bags = Array(k) { br.readLine().toInt() }

    jewels.sortBy { it.first } // 무게에 따라 오름차순 정렬
    bags.sort() 
    val pq = PriorityQueue<Int>(reverseOrder()) 
    var result: Long = 0
    var jIndex = 0

    for (bag in bags) {
        while (jIndex < n && jewels[jIndex].first <= bag) {
            pq.add(jewels[jIndex].second)
            jIndex++
        }
        if (pq.isNotEmpty()) {
            result += pq.poll()
        }
    }

    println(result)
}

배운점

그리디 문제에서 어떻게 효율적으로 해결할 수 있을지를 생각하는 힘을 기르자