프로그래머스 - 입국심사(Lv. 3)

문제 링크

풀이

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    let times = times.sorted() 
    var maxTime = times.last! * n 
    var minTime = 1 
    var result = 0 
    while minTime <= maxTime { 
        let midTime = (minTime + maxTime) / 2 
        var sum = 0 
        times.forEach { sum += midTime / $0 } 
        // print("mid: \(midTime), \(sum)") 
        if sum < n {
            minTime = midTime + 1 
        } else {
            maxTime = midTime - 1 
            result = midTime 
        } 
    } 
    
    return Int64(result)
}

후기

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

보다시피 지문부터가 어마어마한 숫자이다...
시간 복잡도 때문에 결과를 만족해도 계속 타임아웃이 걸려서 많이 해맸던 문제.
바이너리 서치를 이용해서 최대 걸리는 시간부터 차근차근 찾아내면 된다.