입국심사(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명 이하입니다.

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

좋은 웹페이지 즐겨찾기