문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예시
| n | times | return |
|---|---|---|
| 6 | [7, 10] | 28 |
풀이
n으로 주어질 수 있는 최대값이 10억이다. 보통 알고리즘 문제에서 이처럼 큰 값을 반복문으로 돌린다면 시간 초과가 발생할 확률이 매우 높다. 시간 복잡도를 낮추는데에는 또 다시 다양한 기법과 알고리즘이 있지만 그 중에 대표적인 방법 중에 하나가 바로 이분탐색이다. 보통 이분탐색은 O(logN)의 시간복잡도를 보장하기 때문에 완전탐색보다 더 좋은 시간 효율을 보일 수 있다. 따라서 탐색 범위가 위와 같이 매우 크게 주어진다면 이분탐색을 적용하여 해결할 수 있는지 생각해보는 것이 좋다.
이분탐색을 적용하기 위해서는 다만 주의할 점이 하나있다. 바로 이분탐색을 적용할 데이터가 정렬이 되어있어야 한다는 점이다. 이는 이분탐색의 특성자체가 항상 중간값을 기준으로 탐색 범위를 절반씩 좁혀나가는 방식이기 때문에, 정렬이 되어있다는 것을 보장할 수 없는 경우라면 범위를 올바르게 좁혀나갈 수가 없다.
일단 해당문제는 이분탐색이라는 카테고리 하에 있기 때문에 당연히 이분탐색을 적용할 수 있는 케이스일 것 이다. 그러나 실제로 코딩테스트에서 해당 문제를 맞딱이분탐색을 적용할 수 있는 케이스일 것 이다. 그러나 실제로 코딩테스트에서 해당 문제를 맞닥뜨렸다고 가정하고 왜 이분탐색을 적용하여 풀 수 있는지 먼저 살펴보자.
먼저 문제에서 요구하는 것은 모든 사람이 심사받는데 걸리는 시간의 최솟값이다. 이 최솟값이 만족하는 조건은 항상 다음과 같다.
- Min(= 1분) <= 최솟값 <= Max(= Math.max(...times) * n)
즉 문제가 원하는 최솟값은 모든 사람들이 바로 심사를 통과할 수 있는 시간인 1분 ~ 가장 오래걸리는 심사위원의 심사 시간 * 대기인원 사이에 위치하게 된다. 만약 n이 100명이고, times역시 크기가 100일때 모든 심사위원의 처리 속도가 1분일 경우 모든 승객은 1분만에 통과가 가능하다. 반대로 times의 크기가 단 1이라면 단 한명의 심사위원만 있다는 뜻이고, 이는 결국 대기인원 수 x 심사위원의 처리속도 만큼의 시간이 소요될 것 이다. 이를 코드로 나타내면 다음과 같다.
let max = Math.max(...times) * n;
let min = 1;위와 같이 이분탐색에서는 Min 값과 Max 값을 선정할 수 있어야 한다. 또 앞서 말한 정렬조건 역시 충족하는데, Min - Max 사이의 값들은 시간의 흐름이기 때문에 모두 오름차순으로 증가할 것이라는 것이 보장되기 때문이다.
따라서 다음과 같은 이분탐색의 로직을 적용할 수 있다.
- mid(중간값)을 구한다 : (Max + Min) / 2
- mid값으로 주어진 시간 내에 n명을 모두 검사가능한지 체크한다.
- 만약 n명을 모두 체크 가능하다면 주어진 mid 값 보다 더 작은 값으로도 체크 가능한지 다시 검사한다. 즉 Max의 값을
mid-1로 줄인다. - 만약 n명을 모두 체크할 수 없다면 주어진 mid 값을 늘려서 다시 검사해야 한다. 즉 Min의 값을
mid+1로 늘린다. - 위 과정을 Min값이 Max보다 커질때까지 반복한다.
위 반복문을 모두 마치고나서 min에 담긴 값이 결국 우리가 원하는 정답이 될 것이다. 이를 코드로 나타내면 다음과 같다.
...
while(min <= max) {
const mid = Math.floor((max + min) / 2);
const sum = times.reduce((a, b) => a += Math.floor(mid / b), 0);
// reduce를 이용해 주어진 mid값으로 총 몇명 검사가 가능한지 구한다
// 위 과정을 풀이하면 아래와 같다.
// 총 검사가능 인원수 += 주어진 시간 / 각 심사위원의 처리시간
if(sum >= n) max = mid-1;
else min = mid+1;
}해당 문제가 이분탐색을 적용하여 풀이해야 한다는 점과, Min/Max 값을 어떻게 설정하여 이분탐색을 구현할 지 파악할 수 있다면 매우 쉽게 풀이가 가능한 문제이다. 주석을 제외한 전체 코드는 아래와 같다.
코드
function solution(n, times) {
let max = Math.max(...times) * n;
let min = 1;
while(min <= max) {
const mid = Math.floor((max + min) / 2);
const sum = times.reduce((a, b) => a += Math.floor(mid / b), 0);
if(sum >= n) max = mid - 1;
else min = mid + 1;
}
return min;
}출처
