[백준][코틀린][1202] 보석 도둑

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

1202번: 보석 도둑

문제 풀이

1. 보석의 정보를 jewel list 에 (무게, 가격)을 Pair 값으로 저장한다.

2. bag queue 에 가장 무게 정보를 저장한다.

3. jewel list 를 무게를 기준으로 오름 차순으로 정렬한다.

4. bag queue 를 오름 차순으로 정렬한다.

5. bag 의 queue 를 비어질 때 까지 pop 으로 꺼내어 다음의 과정을 수행한다.

6. 초기 index 를 0으로 선언하고 jewel[index].first <= currentBag 이면서 index 가 jewel list 크기보다 작으면 우선순위 queue 에 저장하고 index 를 증가한다. 이때 우선 순위 queue 는 보석의 가격을 기준으로 내림 차순 정렬되게 저장한다.

7. 6번의 탐색을 마친 후 queue 가 비어 있지 않으면 제일 상단 값을 pop 하여 결과에 저장한다. 이때 가격이 최대 1,000,000 이고 보석의 수가 300,000 이므로 최대 가격이 300,000 x 1,000,000 이 될 수 있으므로 Int 범위를 넘어가기 때문에 result 값을 long type 으로 선언하여 저장한다.

8. result 를 출력한다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, K) = br.readLine().split(" ").map { it.toInt() }
    val jewel = mutableListOf<Pair<Int, Int>>()
    val bag = LinkedList<Int>()

    repeat(N) {
        val (M, V) = br.readLine().split(" ").map { it.toInt() }
        jewel.add(Pair(M, V))
    }

    repeat(K) {
        val C = br.readLine().toInt()
        bag.add(C)
    }

    // 보석을 무게를 기준으로 오름 차순 정렬한다.
    jewel.sortWith { a, b ->
        a.first - b.first
    }

    //println("jewel $jewel")

    // 가방의 무게를 오름차순으로 정렬한다.
    bag.sort()

    //println("bag $bag")

    var result = 0L

    // 우선순위 큐를 선언한다.
    val queue = PriorityQueue(Comparator<Pair<Int, Int>>{ a, b ->
        b.second - a.second
    })

    var index = 0

    //가방을 다 쓸때까지 탐색한다.
    while (bag.isNotEmpty()) {
        val currentBag = bag.pop()

        while (index < jewel.size && currentBag >= jewel[index].first) {
            // 보석의 가격을 기준으로 우선 순위 큐에 저장한다.
            queue.add(Pair(jewel[index].first, jewel[index].second))
            index++
        }

        //println("index $index, $queue")

        if (queue.isNotEmpty()) {
            queue.poll()?.let {
                result += it.second
            }
        }
    }

    println(result)
}