function solution(n, times) {
let left = 0
let right = Math.max(...times) * n
while(left < right){
let mid = Math.floor((left+right)/2)
if(n <= getSimsaTime(times,mid)){
right = mid
} else if(n > getSimsaTime(times,mid)){
left = mid + 1
}
}
return right
function getSimsaTime(times,target){
return times.reduce((acc,cur)=>acc+Math.floor(target/cur),0)
}
}
이진탐색을 해야하는 대상이 숨어있다.
우리가 구해야하는 정답인 모든 사람이 심사를 받는데 걸리는 시간
을 이진탐색해서 찾아야 한다.
정답의 범위를 좁혀보자
- 최대: Math.max(...times)
* n
최악의 경우 n
명의 사람이 최대시간 입국심사만 받는 경우이다
lower bound
를 사용해 target
을 구하자
이진탐색 문제에 익숙하지 않기 때문에, 문제를 처음 봤을 때 이게 왜 이진 탐색 문제이지? 뇌정지가 왔었다
입국심사를 기다리는 사람이 최대 1,000,000,000
명이라는 어마어마한 숫자가 될 수 있기 때문에 시간복잡도 O(logN)의 이진탐색으로 풀이해야한다는 추측이 가능하다
최소를 구하는 경우 lower bound
를 구하자