[백준] 11000. 강의실 배정 (Kotlin)

문제 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 

풀이

// [백준] 11000. 강의실 배정 (Kotlin)
import java.util.*
import kotlin.collections.ArrayList

// 강의 클래스
data class C(
    val start: Int,
    val end: Int,
)

fun main() = with(Scanner(System.`in`)){
    val n = nextInt() // 수업 개수
    val arr = ArrayList<C>() // 수업 리스트
    val room = PriorityQueue<Int>() // 강의실

    // 강의 입력
    for(i in 0 until n){
        arr.add(C(nextInt(),nextInt()))
    }

//    arr.sortBy { it.end }
    arr.sortBy { it.start }

    // 강의 입력
    for(i in 0 until n){
        // 처음 강의 넣어주기
        if(i == 0){
            room.add(arr[i].end)
        }
        else{
            // 가장 빨리 끝나는 강의에 넣을 수 있다면 (기존 강의실 사용)
            if(room.peek() <= arr[i].start){
                room.poll()
                room.add(arr[i].end)
            }
            // 새로운 강의실 사용
            else{
                room.add(arr[i].end)
            }
        }
    }

    println(room.size)
}

시간 초과때문에 애먹은 문제이다.

전형적인 그리디 문제인데 N의 범위가 (1 ≤ N ≤ 200,000) 이므로 매우 큰 수가 들어올 것을 생각해야 한다.

강의의 시작, 끝 시간 정보를 담을 강의 클래스를 만들어주고

시작시간 대로 정렬하고, 맨 처음 강의를 우선순위 큐에 넣어준다.

그 후 두번째 강의부터 지금 우선순위큐에 들어있는 가장 빨리 끝나는 강의(peek) 와 비교하여 그 강의실이 빈다면 그대로 사용하고 아니면 새로운 강의실을 배정해주면 된다. 

 

처음에는 arrayList에 end 값들을 저장해서 최솟값이랑 비교해가면서 풀었는데 우선순위큐랑 방식은 같았는데 비효율적인 계산이 들어가서 시간초과가 계속 발생했다.