백준 1781) 컵라면 (PriorityQueue, Comparable 이용)

www.acmicpc.net/problem/1781

1781번: 컵라면

 

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

 

문제번호	1	2	3	4	5	6	7
데드라인	1	1	3	3	2	2	6
컵라면 수	6	7	2	1	4	5	1

 

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

 

 

 

---

문제의 핵심 요소는 바로 다음과 같다.

 

• 한 문제를 풀 때마다 시간은 1씩 올라간다.
• 시간에 맞게 데드라인을 지켜야 하므로 데드라인 순으로 오름 차순 정렬을 한다.
• 데드라인이 같은 문제를 만나게 될 때, 컵라면이 더 많은 문제를 풀어야 최댓값을 얻을 수 있다. (더 큰 값을 욕심낸다. = 그리디 알고리즘)

 

데드라인에 따라 컵라면 수가 결정되기 때문에 이를 한 쌍으로 묶어서(Pair)

각 문제에 대한 데드라인끼리 비교해야 한다.(Comparable)

 

하지만 여기서 문제점은 Collection(array, list, arraylist... 등등) 이나 Queue와 같은 자료구조에

자바나 코틀린에서 제공하는 Pair를 제네릭 타입형으로 이용하면 오류가 발생한다.

 

 val arr = ArrayList<MyPair>()
    val queue = PriorityQueue<Pair<Int,Int>>()

    repeat(n) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        queue.add(a to b)
    }

 

[출력물]

 

 

ClassCastException의 일종으로, Pair 클래스는 Comparable로 캐스트될 수 없다는 오류 메시지가 뜬다.

이는 Pair와 같은 한 쌍 이상의 데이터를 다루는 클래스에다가 Comparable에 implement해서 직접 입력해야 해결할 수있다.

 

 

다음과 같이 말이다.

 

data class MyPair(
    val a: Int,
    val b: Int
) : Comparable<MyPair> {
    override fun compareTo(other: MyPair): Int {
        return when {
            this.a < other.a -> -1
            this.a > other.a -> 1
            else -> 0
        }
    }
}

 

compareTo 메소드를 오버라이드하게 되면 매개변수로 객체 하나가 존재한다.

그리고 Comparable 인터페이스를 ctrl + b(해당 클래스, 혹은 메소드, 혹은 변수로 이동하는 단축키)를 눌러 이동하게 되면,

 

public interface Comparable<in T> {
    /**
     * Compares this object with the specified object for order. Returns zero if this object is equal
     * to the specified [other] object, a negative number if it's less than [other], or a positive number
     * if it's greater than [other].
     */
    public operator fun compareTo(other: T): Int
}

 

위와 같이 뜨는데 이를 간단히 말하자면

 

return 값이

0이라면, 해당 객체 == 다른 객체
1이라면, 해당 객체 > 다른 객체
-1이라면, 해당 객체 < 다른 객체

 

그렇기 때문에 this로 해당 객체를 가리키고, 매개변수의 other로 다른 객체를 가리키면서 위와 같은 룰을 지키면 된다.

 

 

다음으로 PriorityQueue(최소 힙)를 써야 구현하기 편한 이유는

데드라인이 같은 값에 있어서 더 큰 컵라면 수를 정해야 할 때,

PriorityQueue를 이용함으로써 더 작은 값을 추출하면 PriorityQueue에는 큰 값만 남게 된다.

 

이는 Queue의 크기가 곧 시간의 경과를 보여주는 것과 같다!

 

 

또한 다음과 같이 입력이 주어진다면,

 

3 
3   5
3   4
1   2

 

PriorityQueue 상태

1) 데드라인 : 1 이므로 컵라면 : 2 대입 (1초 경과)

 

2) 데드라인 : 3 인데 다음 문제는 시간이 2가 걸리기 때문에 이를 충족. 컵라면 : 4 대입 가능 (2초 경과)

 

 

3) 데드라인 : 3 이므로 컵라면 : 5 대입 (3초 경과)

 

 

 

 

전체 코드는 다음과 같다.

 

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

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = ArrayList<MyPair>()
    val queue = PriorityQueue<Int>()

    repeat(n) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        arr.add(MyPair(a, b))
    }
    arr.sort() // MyPair 클래스 참조
    for (i in arr) {
        
        queue.offer(i.b) // 컵라면 값 대입
        
        if(i.a < queue.size) // 만약 현재 바라보고 있는 문제의 데드라인이 queue의 사이즈보다 작다면
            
            queue.poll()  // 같은 데드라인의 컵라면 수가 들어있으므로 작은 값 추출(큰 값만 남게 됨) 
    }
    println(queue.sum()) // queue에 남아 있는 값을 더한 것이 곧 받을 수 있는 컵라면의 최댓값
}

data class MyPair(
    val a: Int,
    val b: Int
) : Comparable<MyPair> {
    override fun compareTo(other: MyPair): Int {
        return when {
            this.a < other.a -> -1   // a값 기준으로 비교 수행 (데드라인)
            this.a > other.a -> 1
            else -> 0
        }
    }
}