[백준] 11000번: 강의실 배정 - Kotlin[코틀린]

문제

 

11000번: 강의실 배정

 

---

풀이

 

 LectureTime 데이터 클래스를 정의하여 Comparable 인터페이스를 구현한다. 시작시간을 기준으로 오름차순 정렬하도록 고 만약 시작시간이 같다면 종료시간을 기준으로 정렬한다. 입력받은 시간을 LectureTime 배열에 저장하고 이 배열을 정렬해준다.

 

 우선순위 큐를 선언하고 첫번째 수업의 종료 시간을 큐에 넣는다. 배열을 순회하면서 만약 현재 강의의 시작 시간이 우선순위 큐의 최상단의 강의의 종료 시간보다 작거나 같으면 해당 강의는 해당 강의실에서 진행 가능하므로 우선순위 큐에서 poll()해주는 것으로 해당 강의를 빼준다. 또한 현재 종료 시간은 우선순위 큐에 추가한다. 순회가 끝나고 큐에 남아 있는 원소의 개수가 필요한 강의실의 개수이다.

 

정렬된 강의 시간이 1 3 / 2 5 / 3 6 / 4 9 / 5 6 / 6 8인 경우에 강의실을 배정하는 방법은 다음과 같다.

  강의 시간 3 6을 큐에 추가할 때, 1 3의 종료시간인 3을 poll()하면 된다. 최종적으로 큐에는 6, 8, 9 가 남게 되고 3개의 강의실을 사용하는 것을 의미한다.

 

---

코드

 

import java.util.*

data class LectureTime(val start: Int, val end: Int): Comparable<LectureTime> {
    override fun compareTo(other: LectureTime): Int {
        return if (start == other.start) {
            end - other.end
        } else {
            start - other.start
        }
    }
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val classes = Array(num) { LectureTime(0, 0) }
    for(i in 0 until num) {
        with(StringTokenizer(br.readLine())) {
            classes[i] = LectureTime(nextToken().toInt(), nextToken().toInt())
        }
    }
    classes.sort()

    val queue = PriorityQueue<Int>()
    queue.offer(classes[0].end)

    for(i in 1 until num) {
        if(queue.peek() <= classes[i].start) queue.poll()
        queue.offer(classes[i].end)
    }

    bw.write("${queue.size}")
    bw.flush()
    bw.close()
    br.close()
}