[JavaScript] 입국심사
Programmers
2024년 1월 22일
💻 Code
function solution(n, times) {
// 최소시간 1
let left = 1;
// 최대시간
let right = Math.max(...times) * n;
let answer = right;
while (left <= right) {
// console.log(`left: ${left}`)
// console.log(`right: ${right}`)
let mid = Math.floor((left + right) / 2);
// console.log(`mid: ${mid}`)
// 최소시간을 mid로 잡고 몇명 이용가능한지(count) 계산
let count = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);
// console.log(`count: ${count}`)
// console.log('--------------------------');
// mid 값 조정하면서 반으로 줄이기
if (count >= n) {
// count >= n 이면 다 심사를 받을 수 있는 상태이므로 현재까지 찾은 최소 시간 값중 작은 값으로 업데이트
answer = Math.min(answer, mid);
right = mid - 1;
} else {
left = mid + 1;
}
}
return answer;
}
// console.log(solution(6, [7, 10]));
🤔 왜 이문제에 이분탐색을 사용할까?
- 이 문제는 “최소시간”을 찾는 최적화 문제, 최소 시간이 어디에 있을지 알 수 없으므로 가능한 모든 시간을 검색해야 한다.
- 이 경우 최소 시간(left), 최대 시간(right) 사이에서 원하는 결과를 찾을 수 있는 이분탐색이 적합하다.
- 이분탐색의 경우 시간복잡도가 O(logN)이기 때문에, 심사관의 수나 대기 인원 수가 많아도 빠르게 원하는 결과를 얻을 수 있다.