[백준] 1931번: 회의실 배정 - Kotlin[코틀린]

문제

 

1931번: 회의실 배정

 

---

풀이

 

 이 문제의 유형은 활동 선택 문제(Activity Selection problem)라고하며 대표적인 그리디 문제이다. 활동 선택 문제란 각 활동의 시작 시간과 종료 시간이 주어졌을 때, 한 사람은 한 번에 하나의 활동만 수행할 수 있다고 가정하며, 한 사람이 최대로 수행할 수 있는 활동의 수를 찾는 것을 목표로 하는 것이다.

 

 선택할 수 있는 활동이 많아지려면, 서로 겹치지 않는 활동에 대해 종료시간 빠른 경우를 선택해야 한다. 따라서 활동들을 종료시간을 기준으로 정렬하고 선택한다. 가장 먼저 종료하는 활동을 선택하고, 두 번째 활동부터 활동의 시작 시간이 마지막으로 선택한 활동의 종료 시간보다 크거나 같으면 선택한다. 아래 그림을 예시로 들면 1 - 3 - 4 - 6 - 7 - 9 - 10 을 선택해야 최대로 수행할 수 있다.

 

 입력받은 시간을 배열에 저장하고 sortWith 함수를 이용해 정렬했다. 종료 시간이 같은 경우에는 시작 시간이 빠른 순으로 정렬한다. forEach문을 통해 시간들을 확인하면서 현재 종료 시간보다 시작 시간이 크거나 같으면 그 회의의 종료 시간을 기록하고 회의 수를 증가시킨다.

 

---

코드

 

import java.util.*

data class Time(val start: Int, val end: Int)

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

    val num = br.readLine().toInt()
    val arr = Array(num){ Time(0, 0) }

    for(i in 0 until num) {
        val line = StringTokenizer(br.readLine())
        arr[i] = Time(line.nextToken().toInt(), line.nextToken().toInt())
    }

    arr.sortWith { d1, d2 ->
        if (d1.end == d2.end) d1.start - d2.start
        else d1.end - d2.end
    }

    var cnt = 0 // 회의 수
    var current = 0 // 현재 종료 시간

    arr.forEach {
        if(current <= it.start) {
            current = it.end
            cnt++
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}