프로그래머스-이분탐색: 입국심사(Javascript)

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43238

문제

문제를 해결한 방법

이분탐색 문제로 저는 다음과 같이 풀이했습니다.

1. times를 오름차순으로 정렬시킨다.
2. 가장 늦게 끝나는 시간을 구한다
   • 가장 오래걸리는 심사대 * n
3. 이분탐색으로 해당 시간에 각 심사대의 최대 심사 수의 합 인 count 를 구한다.
4. count >= n 인 경우
   1. 최솟값을 갱신한다.
   2. mid의 왼쪽을 탐색한다.
      • right = mid-1;
5. count < n 인 경우
   1. mid의 오른쪽을 탐색한다.
      • left = mid+1

예시

문제 예시처럼 입력값이 n=6 times=[7,10] 인 경우

1. times를 오름차순으로 정렬시킨다.
2. 가장 늦게 끝나는 시간을 구한다 -> 60초(= 10*n)
3. 이분탐색으로 처음 mid는 30초이다. (left: 0 , right: 60) // 1부터 해도 됨
   • 30초에 각 심사대는 4명(30/7), 3명(30/10) 총 7명을 심사한다.
4. 7 >= n 이므로 min을 30으로 갱신하고 mid의 왼쪽을 탐색한다.
   • 탐색범위 (left: 0 , right: 29)
   • mid = 14
5. 이분탐색이 끝날 때 까지 3,4번 을 반복한다.
6. min을 리턴한다.

소스 코드

const binarySearch= (times, n) =>{
    let left = 0;
    let right = times[times.length-1] * n;
    let mid = Math.floor((left+right) / 2);
    let min = right;
    
    while(left <= right){
        const count = times.reduce((acc, el) => acc+= Math.floor(mid / el), 0);
        if(count >= n){
            min = Math.min(min, mid);
            right = mid-1;
        }else
            left = mid+1;
        
        mid = Math.floor((left+right) / 2);
    }
    return min;
}

function solution(n, times) {
    times.sort((a,b) => a-b);
    return binarySearch(times, n);
}