[백준 1202번] [Kotlin] 보석 도둑

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

1202번: 보석 도둑

 

난이도 : 골드 2
태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

 

 

설명

정렬과 우선순위 큐를 사용해 풀 수 있습니다.

 

보석의 경우, 무게로 내림차순 정렬하고, 무게가 같을 경우 오름차순 정렬을 합니다.

가방도 무게를 기준으로 오름차순 정렬하고,

 

각 가방의 무게보다 가볍거나, 같은 보석의 가격을 우선순위 큐(내림차순)에 넣고, 큐가 비어있지 않으면 하나를 뺍니다

 

 

 

소스코드

import java.util.Collections
import java.util.PriorityQueue

data class Jewelry(val weight: Int, val price: Int) : Comparable<Jewelry> {
    override fun compareTo(other: Jewelry): Int {
        return if (this.weight != other.weight) this.weight - other.weight // 무게로 내림차순 정렬
        else other.price - this.price // 무게가 같으면 가격으로 오름차순 정렬
    }
}

fun main() {
    val br = System.`in`.bufferedReader()
    // n - 보석의 수, k - 가방의 수
    val (n, k) = br.readLine().split(" ").map { it.toInt() }

    val pqJewelries = PriorityQueue<Jewelry>()
    val bag = Array(k) { 0 }

    repeat(n) {
        val (w, p) = br.readLine().split(" ").map { it.toInt() }
        pqJewelries.add(Jewelry(w,p))
    }
    repeat(k) {
        bag[it] = br.readLine().toInt()
    }

    // 무게 기준으로 오름차순 정렬
    bag.sort()

    // 가격을 넣을 우선순위 큐. 가격이 높은 순으로 정렬
    val pqPrice = PriorityQueue<Int>(Collections.reverseOrder())
    var total = 0L

    bag.forEach { bagWeight ->
        while (pqJewelries.isNotEmpty()) {
            if(pqJewelries.peek().weight <= bagWeight) {
                pqPrice.add(pqJewelries.poll().price)
            } else {
                break
            }
        }
        
        // 가장 비싼 값 하나를 꺼냄 (배낭 하나당 한개의 보석만 들어갈 수 있기 때문에 하나만)
        if (pqPrice.isNotEmpty()) total += pqPrice.poll()
    }

    println(total)
}

 

 

 

후기

코드에 별 문제가 없는 것 같은데 계속 틀렸습니다가 뜨길래 뭐지 했더니

total을 Int형에서 Long 형으로 고치니 맞았네요.

 

범위 체크는 기본적인건데 항상 놓치는 부분이네요... 좀 더 신경써야 겠습니다.