[Kotlin, Lv.3] 프로그래머스 입국심사

출처: unsplash.com

 

입국심사

Level 3

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=kotlin

 

문제 내용

 

 

문제 접근

이분 탐색을 이용해야 하는 문제이다.

어디서 이분 탐색을 써야 할까?

 

n명을 검사하는 데 총 걸리는 시간을 기준으로 이분 탐색을 진행해야 한다.

총 걸린 시간을 어떻게 구할 수 있을까?

예제 1에서는 n = 6이고, 심사관이 검사하는 데 드는 시간 10초, 7초이고 걸린 시간이 28초이다.

 

28초가 나오기 위해서는 7초 걸리는 심사관이 4명을 검사하고, 10초 걸리는 심사관이 2명을 검사하면 딱 6명이 돼서 검사를 끝낼 수 있다.

이 사실로 다음과 같은 공식을 적용할 수 있다.

28 / 4 + 28 / 10 = 6

걸린 시간에 각 심사관의 검사시간을 나누고 나머지는 버린 값의 합이 n과 같아야 정확한 총 검사시간이 나온다.

이를 이용해 이분 탐색으로 코드를 짜보겠다.

 

이분 탐색에는 시작점과 종료점이 있다.

시작점은 0으로 하고, 종료점을 n명이 검사받았을 때, 가장 오래 걸리는 검사 시간으로 설정하면 된다.

가장 오래 걸리는 시간을 구하려면 가장 검사가 오래 걸리는 심사관의 검사 시간에 n을 곱하면 된다.

binarySearch(0, examiner.last() * people)

 

<조건 1>

다음으로 이분 탐색을 진행하면서 시작점과 종료점을 변경해야 하는 경우이다.

시작점이 변경되려면 mid(현재 검사 시간)를 이용해 검사할 수 있는 사람들이 n보다 적은 경우에는 시작점을 mid + 1로 변경해 탐색 범위를 좁힐 수 있다.

val mid = (end + start) / 2L
val res = examiner.sumOf { mid / it }

if (res < people)

 

 

<조건 2>

만약 mid를 이용해 검사할 수 있는 사람이 n보다 크거나 같은 경우에는 종료점을 줄여서 검색 범위를 좁혀야 한다. 종료점을 mid - 1로 변경한다. 어차피 mid 이후의 값들도 모두 검사할 수 있는 사람이 n보다 클 것이기 때문이다.

n과 mid로 검사할 수 있는 사람의 수가 같아야 정답이 된다.

이 조건에 들어오면 정답 후보가 되어 answer에 저장된다. 하지만 answer가 바뀔 수도 있다.

else {
    answer = mid
    binarySearch(start, mid - 1)
}

 

 

문제 해결 코드

private var examiner = listOf<Long>()
private var people = 0
private var answer: Long = 0

fun solution(n: Int, times: IntArray): Long {
    times.sort()
    examiner = times.map { it.toLong() }
    people = n

    binarySearch(0, examiner.last() * people)
    println(answer)

    return answer
}

private fun binarySearch(start: Long, end: Long) {
    if (start > end) return

    val mid = (end + start) / 2L
    val res = examiner.sumOf { mid / it }

    if (res < people) {
        binarySearch(mid + 1, end)
    } else {
        answer = mid
        binarySearch(start, mid - 1)
    }
}

 

문제 풀이

times를 정렬한 값을 examiner에 저장한다.

그리고 binarySearch 함수를 수행한다.

 

binarySearch는 end가 start보다 작아진다면 종료된다.

end와 start의 중간값인 mid를 생성한다. mid가 총 걸린 시간이 될 것이다.

examiner와 mid를 이용해 mid분 동안 검사할 수 있는 사람이 몇 명인지 구한다.

그리고 조건 1을 만족한다면 start의 범위를 mid + 1로 설정하고 그렇지 않다면 조건 2를 적용해 end를 mid - 1로 설정하고 재귀한다.

 

 

문제 해결 과정

search를 하기 위해 어떤 것을 써야 할지 감이 잡히지 않아서 접근법을 찾아서 해결하였다.

걸린 시간을 검색하는 것과 걸린 시간과 검사 시간으로 검사할 수 있는 사람이 몇 명인지 구할 수 있다는 사실도 알게 되었다.