프로그래머스: 입국 심사 (Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

프로세스

1. 걸리는 시간(제한 시간)을 기준으로 이분 탐색을 한다.
2. 제한 시간 안에 총 몇 명을 심사할 수 있는지 확인한다.
   1. if (심사된 인원 >= 입국 인원) --> end = mid - 1 (최소 값을 구하기 위해)
   2. else --> start = mid + 1 (제한 시간이 짧아서 전부 검사할 수 없기 때문)
3. 이분 탐색이 끝나면 start를 반환한다.

풀이

처음엔 우선순위 큐를 이용하는 방법을 시도했다. pq에서 뺄 때마다 지금까지 걸린 시간 += 검사 시간, 검사한 인원이 n보다 클 때까지 진행하는 방식이었다. 그런데 최악의 경우 시간 복잡도가 10억(명) * log(십만)이라 그런지 시간 초과가 났다.

 

이 문제는 대놓고 이분 탐색 카테고리에 있던 문제였어서 이분 탐색에 초점을 맞추고 접근해봤다.

뭘 기준으로 이분 탐색을 할 수 있을까..

 

경험상 직관적이지 않던 이분 탐색 문제들은 모두 정답이 될 것을 기준으로 두고 있었다. 그래서 걸리는 시간을 기준으로 생각해봤다. 시간을 정해놓고, 시간 안에 모든 인원을 심사할 수 있는지 확인하는 것이다.

 

제한 시간 안에 모두 심사할 수 있는지는 심사관마다 걸리는 시간을 제한 시간으로 나누면 구할 수 있다. 시간 복잡도는 O(심사관 수)이다.

/**
 * 제한 시간 안에 모두 검사할 수 있는지 확인한다
 * @param) time: 제한 시간
 */
fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
    var checkCount: Long = 0

    for (checkTime in officers) {
        checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
    }

    return if (checkCount >= numOfPeople) true else false
}

이분 탐색의 범위

• 최소 시간: 심사관 수 >= 입국자 수, 각 심사관이 검사하는데 걸리는 시간 1분 -> 1분
• 최대 시간: 심사관 1명, 심사 시간 10억 분, 입국자 10억 명 -> 10억 * 10억 분

const val MAX_SIZE: Long = 1_000_000_000
...
var start: Long = 1
var end: Long = MAX_SIZE * MAX_SIZE

탐색 범위 좁히기

걸리는 시간의 최소 값을 구하는 것이므로

• 시간 안에 모두 심사 가능 -> 더 짧은 시간에 대해 확인해보기 위해 end = mid - 1
• 불가능 -> 현재 시간이 너무 짧다는 의미이므로 start = mid + 1로 범위를 좁혀나간다.

그리고 이분 탐색이 종료됐을 때 start 값이 구하고자 하는 답이 된다.

코드

/* 걸린 시간을 기준으로 이분 탐색 */

import java.util.*

const val MAX_SIZE: Long = 1_000_000_000

class Solution {
    fun solution(n: Int, times: IntArray): Long {
        var start: Long = 1 // 심사관 >= 입국자, 검사 시간: 1분
        var end: Long = MAX_SIZE * MAX_SIZE // 심사관: 1명, 검사 시간: 10억 분, 입국자: 10억 명
        
        while(start <= end) {
            val mid = (start + end) / 2

            if (isPossibleInTime(mid, times, n)) {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }
        
        return start
    }
    
    /**
     * 제한 시간 안에 모두 검사할 수 있는지 확인한다
     * @param) time: 제한 시간
     */
    fun isPossibleInTime(time: Long, officers: IntArray, numOfPeople: Int): Boolean {
        var checkCount: Long = 0
        
        for (checkTime in officers) {
            checkCount += time / checkTime // 해당 심사관이 시간 안에 검사할 수 있는 인원 수
        }
        
        return if (checkCount >= numOfPeople) true else false
    }
}