[백준 1931번] [Kotlin] 회의실 배정

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

1931번: 회의실 배정

 

난이도 : 실버1
태그 : 그리디, 정렬

 

 

설명

가장 많은 회의를 배정할 수 있도록 하는 문제입니다.

 

처음엔 회의 시간이 가장 짧은 것 부터 그리디 알고리즘을 이용하여 풀이하였는데,

 

생각해보니 (1,10) (9,11) (10, 20)의 경우

 

(1,10) (10,20)을 냅두고 (9,11)을 선택하게 되더군요.

 

그래서 끝나는 시간이 가장 짧은 순으로 그리디 알고리즘을 적용하였습니다.

 

 

 

소스코드

인풋값 저장

val n = readLine()!!.toInt()
val arr = Array(n) { Array(2) { 0 } }

repeat(n) {
    val line = readLine()!!.split(" ")
    arr[it][0] = line[0].toInt()
    arr[it][1] = line[1].toInt()

}

이차원 배열 arr을 선언 및 생성합니다.

arr[n][0] 은 시작시간을, arr[n][1]은 끝나는 시간을 담습니다.

 

정렬

arr.sortWith(compareBy<Array<Int>> { it[1] }.thenBy { it[0] })

 

끝나는 시간 기준으로 정렬을 합니다.

만약, 끝나는 시간이 같을 경우 시작시간을 기준으로 정렬합니다.

 

이전 회의의 끝나는 시간과, 다음 회의의 시작시간을 비교할 것인데,

(1,1)(0,1) 과 같은 값이 들어왔을 경우

끝나는 시간이 1인데, 다음 회의의 시작시간이 0이기 때문에 넘겨버리는 문제가 발생하기 때문입니다.

 

끝나는 시간이 같을 경우 시작시간을 기준으로 정렬을 하여 (0,1)(1,1) 과 같이 정렬을 하면

(0,1)(1,1) 모두 카운트 할 수 있습니다.

 

 

가능한 회의의 수 계산

var time = arr[0][1]
var cnt = 1

for (i in 1 until arr.size) {
    if (time <= arr[i][0]) {
        time = arr[i][1]
        cnt++
    }
}

println(cnt)

이전 회의의 끝 시간과, 다음 회의의 시작 시간을 비교합니다.

만약 다음 회의의 시작시간과 이전 회의의 끝나는 시간이 같거나, 다음 회의의 시작시간이 더 크다면

time 변수에 다음 회의의 끝나는 시간을 대입하고

cnt를 1만큼 증가시킵니다.

 

마지막으로, cnt를 출력하면 됩니다.

 

전체 소스코드

fun main() {
    val n = readLine()!!.toInt()
    val arr = Array(n) { Array(2) { 0 } }

    repeat(n) {
        val line = readLine()!!.split(" ")
        arr[it][0] = line[0].toInt()
        arr[it][1] = line[1].toInt()

    }

    arr.sortWith(compareBy<Array<Int>> { it[1] }.thenBy { it[0] })

    var time = arr[0][1]
    var cnt = 0

    for (i in 1 until arr.size) {
        if (time <= arr[i][0]) {
            time = arr[i][1]
            cnt++
        }
    }

    println(cnt + 1)
}

 

 

후기

2, 2 처럼 시작시간과 끝나는 시간이 같은 값이 들어오면,

회의가 시작과 동시에 끝난다고 생각하면 된다는데,

시작과 동시에 끝나는 회의라니.... 하... 부럽습니다....ㅠㅠ