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

문제 풀이 아이디어

저만의 습관인지는 모르겠지만 저는 문제를 읽자마자 문제에 나온 그대로 코드로 옮기고자 하는 버릇이 있습니다. 이 문제 역시 예시가 주어진대로 시간이 흐름에 따라 심사관이 한명한명 처리하는 것을 그대로 코드로 옮기는 것 (시뮬레이션)으로 문제를 풀려고 했었습니다.

하지만 문제를 풀 때는 더 효과적인 방법은 없는지 고민하고 시작해야 합니다. 문제의 본질을 파악하는 것에서 그 시작해야할 것입니다.

이 문제에서 구하는 값은 최소한의 심사 시간입니다. 물론 시뮬레이션을 통해서 최소한의 심사 시간을 구할 수 있겠지만 그렇게 한다면 [1, 1, 10000000] 같은 입력이 들어오는 경우 예외처리는 엄청나게 복잡하게 됩니다.

따라서 관점을 전환해서 어떤 심사 시간 안에 모든 심사를 할 수 있는지를 판단하는 문제로 바꾸어서 풀어야 합니다. 특정 숫자를 구하는 문제를 OX 문제로 바꾸어서 푸는 것이죠. 주어진 심사 시간 안에 몇 명의 사람을 심사할 수 있는지 구하는 것은 간단하니 이 OX 문제는 시뮬레이션 보다는 훨씬 간단한 코드로 해결할 수 있습니다.

여기까지 들으니 떠오르는 알고리즘이 하나 있을 것입니다. 바로 특정 범위에서 이분탐색을 통해 원하는 수를 구하는 파라메트릭 서치입니다.

코드

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var start = 1
    // 최대 범위는 모든 사람들이 가장 느린 심사관에게 검사를 받을 때
    var end = times.max()! * n
    var ans = 0
    
    // 파라메트릭 서치
    while start <= end {
        let mid = (start + end) / 2
        var count = 0
        
        // 심사관 별로 mid 시간동안 검사할 수 있는 사람의 수 세기
        for time in times {
            count += mid / time
            
            // 빠른 심사관들이 전부 처리할 수 있으면 break
            if count >= n { break }
        }
        
        // mid 시간 안에 심사할 수 있는 경우
        if count >= n {
            ans = mid
            end = mid - 1
        // mid 시간 안에 심사할 수 없는 경우
        } else {
            start = mid + 1
        }
    }
    
    return Int64(ans)
}