문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
이분탐색
정렬되어 있는 배열에서 데이터를 찾으려고 시도할 때, 순차탐색처럼 처음부터 끝까지 데이터를 모두 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾는 검색 방법이다.
시간복잡도 : O(logn)
풀이
시간을 기준으로 이분탐색하여 적합한 시간을 찾아야 한다. 최소시간은 0, 최대시간은 입국심사에 걸리는 최대시간 * 입국심사 인원으로 초기화 했다. 최대시간과 최소시간의 합을 2로 나눠 중간값을 잡고, 그 시간에 검사대를 통과할 수 있는 인원을 계산한다. 통과할 수 있는 인원이 통과해야하는 인원보다 크다면 max 값을 mid -1의 값으로 업데이트 해주고 ans의 값을 mid 값으로 업데이트 해준다. 반대로 통과해야하는 인원이 더 많다면 min 값을 mid +1 의 값으로 업데이트 해준다. 모든 사람이 검사를 받는데 걸리는 시간의 최소 시간을 구해야 하므로 min <= max를 만족할때 까지 비교를 해주면서 값을 찾는다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const solution = (n, times) => {
times.sort((a, b) => a - b);
let ans = Infinity;
let min = 0;
let max = times[times.length - 1] * n;
while (min <= max) {
const cur = Math.floor((min + max) / 2);
const curPeople = times.reduce((preValue, curValue) => {
return preValue + Math.floor(cur / curValue);
}, 0);
if (curPeople < n) min = cur + 1;
else {
if (cur <= ans) ans = cur;
max = cur - 1;
}
}
return ans;
};
이분탐색 카테고리로 분류되어있어 이분탐색을 사용하여 문제를 해결하기위해 접근했다. 만약 카테고리에 이분탐색이라고 적혀있지 않았다면 이분탐색으로 해결해야 된다는 것을 찾지 못하고 많은 시도를 하다가 못풀었을 수도 있겠다는 생각을 했다.