입국심사(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명 이하입니다.
보다시피 지문부터가 어마어마한 숫자이다...
시간 복잡도 때문에 결과를 만족해도 계속 타임아웃이 걸려서 많이 해맸던 문제.
바이너리 서치를 이용해서 최대 걸리는 시간부터 차근차근 찾아내면 된다.
Author And Source
이 문제에 관하여(입국심사(Lv. 3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@haze5959/프로그래머스-입국심사Lv.-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)