[백준] 1931 (회의실 배정)

#1 알고리즘

#1-1 그리디 알고리즘

그리디 알고리즘 (Greedy Algorithm)

 

#1-2 최적해

가장 많은 회의 갯수가 최적해다. 딱 봐도 정렬을 요구하는 문제다. 회의를 시작 시각 기준으로 정렬하면 문제가 동적 프로그래밍 문제가 된다. 반면, 종료 시각을 기준으로 정렬하면 문제가 그리디 알고리즘 문제가 된다. 전자의 접근이 틀렸다고는 볼 수 없지만 시간 초과로 인해 문제 풀이가 불가능하다. 따라서 종료 시각을 기준으로 정렬해야 한다. 또, 일반적으로 그리디 알고리즘은 시간 복잡도가 동적 프로그래밍보다 낮으므로 둘 다 사용 가능한 경우 그리디 알고리즘이 비교 우위를 가진다.

 

#1-3 병합 정렬

정렬 - 병합 정렬 (Merge Sort)

배열의 정렬을 위해 병합 정렬을 사용했다.

 

#2 여담

사실 이 문제는, "그리디 알고리즘을 알고 있는가?"보단 "회의 종료 시각을 기준으로 정렬할 생각을 할 줄 아는가?"라고 묻는 문제다. 무심코 시작 시각을 기준으로 정렬하면 동적 프로그래밍 접근법에 생각이 함몰되어 버린다. 눈에 첫째로 보이는 것을 정렬 기준으로 삼는 버릇을 고쳐야 한다는 교훈을 주는 문제다.

 

#4의 코드처럼 나는 처음에 동적 프로그래밍을 통해 문제 풀이를 시도했으나 번번히 시간 초과가 나 실패했다. #4 풀이의 시간 복잡도가 O(n²)라는 것을 처음 풀 때 눈치챘더라면, 다른 접근법도 고려해볼 수 있었을 것이다.

 

#3 코드 - 코틀린

var meetingCount = -1
lateinit var meetings: Array<Pair<Int, Int>>
lateinit var cached: Array<Int>

fun main() {
    meetingCount = readln().toInt()
    meetings = Array(meetingCount) { Pair(-1, -1) }
    cached = Array(meetingCount) { -1 }
    for (i in 0..<meetingCount) {
        val meetingString = readln().split(" ")
        meetings[i] = Pair(meetingString[0].toInt(), meetingString[1].toInt())
    }

    mergeSort(meetings, 0, meetings.size - 1)

    var tempCount = 1
    var lastMeetingEndTime = meetings[0].second
    for (i: Int in 1..<meetingCount) {
        if (lastMeetingEndTime <= meetings[i].first) {
            tempCount++
            lastMeetingEndTime = meetings[i].second
        }
    }

    println(tempCount)
}

fun mergeSort(array: Array<Pair<Int, Int>>, startIndex: Int, endIndex: Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if (startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array: Array<Pair<Int, Int>>, startIndex: Int, midIndex: Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T: Array<Pair<Int, Int>> = Array(endIndex - startIndex + 1) { Pair(0, 0) }
    var t = 0

    while (f <= midIndex && s <= endIndex) {

        // 만약 array[f] < array[s] 라면
        if (isSecondGreaterThanFirst(array[f], array[s])) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    // f의 영역이 남았다면 비워준다
    while (f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while (s <= endIndex) {
        T[t++] = array[s++]
    }

    for (i: Int in 0..(T.size - 1)) {
        array[startIndex + i] = T[i]
    }
}

fun isSecondGreaterThanFirst(pair1: Pair<Int, Int>, pair2: Pair<Int, Int>): Boolean {
    if (pair1.second < pair2.second) {
        return true
    }

    if (pair1.second == pair2.second && pair1.first < pair2.first) {
        return true
    }

    return false
}

 

#4 실패한 코드 - 시간 초과 - 코틀린

var meetingCount = -1
lateinit var meetings: Array<Pair<Int, Int>>
lateinit var cached: Array<Int>

fun main() {
    meetingCount = readln().toInt()
    meetings = Array(meetingCount) { Pair(-1, -1) }
    cached = Array(meetingCount) { -1 }
    for (i in 0..<meetingCount) {
        val meetingString = readln().split(" ")
        meetings[i] = Pair(meetingString[0].toInt(), meetingString[1].toInt())
    }

    mergeSort(meetings, 0, meetings.size - 1)

    for (i: Int in 0..<meetingCount) {
        recursiveTraversal(i, 0)
    }

    println(cached.max())
}

fun recursiveTraversal(index: Int, previousMeetingCountSum: Int) {
    if (meetingCount <= index) {
        return
    }

    val sum = previousMeetingCountSum + 1

    cached[index] = if (cached[index] == -1) {
        sum
    } else {
        if (sum <= cached[index]) { // 가지치기
            return
        } else {
            sum
        }
    }

    var leastNextIndex = -1
    for (nextIndex: Int in (index + 1)..<meetingCount) {
        if (meetings[index].second <= meetings[nextIndex].first) {
            leastNextIndex = nextIndex
            break
        }
    }

    if (leastNextIndex != -1) {
        for (i: Int in leastNextIndex..<meetingCount) {
            recursiveTraversal(i, sum)
        }
    }
}

fun mergeSort(array: Array<Pair<Int, Int>>, startIndex: Int, endIndex: Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if (startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array: Array<Pair<Int, Int>>, startIndex: Int, midIndex: Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T: Array<Pair<Int, Int>> = Array(endIndex - startIndex + 1) { Pair(0, 0) }
    var t = 0

    while (f <= midIndex && s <= endIndex) {

        // 만약 array[f] < array[s] 라면
        if (isSecondGreaterThanFirst(array[f], array[s])) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    // f의 영역이 남았다면 비워준다
    while (f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while (s <= endIndex) {
        T[t++] = array[s++]
    }

    for (i: Int in 0..(T.size - 1)) {
        array[startIndex + i] = T[i]
    }
}

fun isSecondGreaterThanFirst(pair1: Pair<Int, Int>, pair2: Pair<Int, Int>): Boolean {
    if (pair1.first < pair2.first) {
        return true
    }

    if (pair1.first == pair2.first && pair1.second < pair2.second) {
        return true
    }

    return false
}

이 문제와 유사한 방식(상향식 동적 프로그래밍)으로 풀려고 시도했으나 시간 초과가 난 코드다. #3과 달리 isSecondGreatorThanFirst()가 Pair.first를 먼저 정렬한다.