[Kotlin] 백준 26215 : 눈 치우기

문제 링크

26215번: 눈 치우기

---

---

문제 해설

정렬을 이용하여 풀 수 있는 문제다. 우선 문제의 조건에 따라 분당 치울 수 있는 눈은 한집만 1 또는 두 집에서 각각 1씩, 총 2를 치울 수 있다. 따라서 한 집 앞에 쌓인 눈의 양이 1440을 초과한다면 무슨 수를 쓰더라도 24시간 내에 치울 수 없기 때문에 -1을 출력하고 프로그램을 종료한다.(코드의 11~14번째 줄)

 

그 외의 경우는 각 집 앞에 눈이 쌓인 양을 내림차순으로 정렬하여 해결한다. 눈이 쌓인 양이 가장 많은 집과 두 번째로 많이 쌓인 집을 선택하여 두 집에서 두 번째로 많이 쌓인 눈의 양만큼 모두 치운다. 기존에 눈이 가장 많이 쌓였던 집은 남은 눈만큼 다시 집을 모아놓은 집합에 넣고 치운 눈의 양만큼 소요 시간에 추가한다. 이후 최종적으로 계산된 소요 시간이 1440을 초과한다면 -1을, 1440 이하라면 소요 시간을 그대로 출력하면 된다.

 

눈을 치울 때마다 정렬을 해줘야하기 때문에 우선순위 큐를 이용한 최대 힙으로 구현했다.

---

Code

import java.util.PriorityQueue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val snow = PriorityQueue<Int>(reverseOrder())
    var minute = 0
    readLine()
    StringTokenizer(readLine()).run {
        while (hasMoreTokens()) {
            nextToken().toInt().let {
                if (it > 1440) {
                    println(-1)
                    return@with
                }
                snow.add(it)
            }
        }
    }

    while (snow.size > 1) {
        val max = snow.poll()!!
        val secondMax = snow.poll() ?: 0
        snow.add(max - secondMax)
        minute += secondMax
    }
    minute += snow.poll() ?: 0
    println(if (minute > 1440) -1 else minute)
}