[Kotlin, G5] 백준 11000번 강의실 배정

출처: unsplash.com

 

강의실 배정(11000번)

Gold 5

#자료 구조 #그리디 알고리즘 #정렬 #우선순위 큐

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

 

문제 내용

 

 

문제 접근

강의실을 최대한 적게 사용해 n개의 수업을 모두 진행해야 한다.

강의의 시작 시간과 종료 시간을 참고해 모든 강의를 진행하는 데 필요한 최소 강의실의 개수를 구해야 한다.

 

각각의 강의들 중 강의 시작 시간이 강의 종료 시간보다 작거나 같을 때는 한 강의실에서 같이 들을 수 있다.

예를 들어 시작 시간이 1이고 종료 시간이 3인 강의와 시작 시간이 3이고 종료 시간이 5인 강의는 한 강의실에서 같이 들을 수 있다. 

 

강의들 중 제일 먼저 시작하는 강의부터 시작해 한 강의실에서 쓸 수 있는 강의들을 모두 제거하면서 문제를 해결하면 된다.

예를 들어 다음과 같은 입력 예제가 있을 때

3
1 3
2 4
3 5

1에 시작하고 3에 끝나는 강의부터 시작해 한 강의실에서 쓸 수 있는 강의인 3에 시작하고 5에 끝나는 강의를 제거하면 된다.

그리고 위 과정을 반복하면 필요한 최소 강의 수를 알 수 있게 된다.

 

강의의 개수가 많은 케이스에서는 일일이 찾는 방법을 사용하면 시간 초과가 발생할 수 있다.

강의가 최대 20만 개가 올 수 있기 때문에 시간 초과가 발생할 것이다.

 

그러므로 선택된 강의에서 시작할 수 있는 강의를 빠르게 찾아야 하는데 나는 이분 탐색을 이용해서 강의를 찾아 주었다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    val lecture = mutableListOf<Pair<Int, Int>>()

    for (i in 0 until n) {
        val (s, t) = bf.readLine().split(" ").map { it.toInt() }
        lecture.add(Pair(s, t))
    }

    lecture.sortBy { it.second }
    lecture.sortBy { it.first }

    var classCnt = 1
    var endTime = lecture.first().second
    lecture.removeFirst()

    while (lecture.isNotEmpty()) {
        val bsResIndex = binarySearch(lecture, endTime, 0)

        if (bsResIndex in lecture.indices) {
            endTime = lecture[bsResIndex].second
            lecture.removeAt(bsResIndex)
        } else {
            classCnt++
            endTime = lecture[0].second
            lecture.removeFirst()
        }
    }

    println(classCnt)
}

private fun binarySearch(list: List<Pair<Int, Int>>, endTime: Int, si: Int, ei: Int = list.lastIndex): Int {
    val mi = (si + ei) / 2
    if (si > ei) return si

    return if (list[mi].first >= endTime) binarySearch(list, endTime, si, mi - 1)
    else binarySearch(list, endTime, mi + 1, ei)
}

 

문제 풀이

우선 이분 탐색을 사용하기 위해 강의를 정렬해 주었다.

그리고 정답은 무조건 1 이상이기 때문에 classCnt를 1로 정하고, 처음 선택된 강의의 종료 시간을 저장할 변수를 만들어 준다.

첫 번째 index를 지우고 반복을 진행한다.

 

이분 탐색을 통해 endTime과 시작 시간이 크거나 같은 강의들 중 가장 작은 강의의 index를 불러와 줬다.

이분 탐색의 결과가 lecture의 범위를 벗어나게 되면 더 이상 같은 강의실을 쓸 수 있는 강의가 없다는 뜻이기 때문에 현재 남은 강의들 중 첫 번째 강의의 종료 시간을 endTime에 재적용하고 classCnt를 증가시킨다.

첫 번째 값을 지우는 것을 잊지 말자.

 

이분 탐색을 통해 정상적으로 index를 불러온 경우에는 선택된 index의 강의 종료 시간으로 endTime을 정의해 주고 해당 index의 값을 제거한다.

 

 

문제 해결 과정

이분 탐색이 알고리즘 키워드에는 없었으나, 이분 탐색을 사용해서 해결했다.

아직 우선순위 큐를 정확히 모르기 때문에 어떻게 구현할까 생각하다가 이분 탐색을 떠올리게 되었다.

 

아이디어 자체는 떠올리기도 어렵지 않았고, 구현 자체도 어렵지는 않았다.

체감 난이도: Silver 1 ~ Gold 5