[프로그래머스 Lv.3] 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238?language=javascript 

코딩테스트 연습 - 입국심사

const binarySearch = (times, n) => {
    let left = 0;
    let right = n * times[times.length - 1];
    let middle, people;
    
    while(left <= right) {
        middle = Math.floor((left + right) / 2);
        
        people = times.reduce((prev, cur) => prev + Math.floor(middle/cur), 0);
        
        if(people >= n) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    
    return left;
}

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

이분탐색 문제이다. 

 

입력을 예로들면 최소시간을 구하는 문제이므로 최소값(left)는 1로 두고, 최대값은 정렬된 times배열의 마지막 값에 인원수를 곱한 값을 넣어주자.  right = 10 * 6 = 60

 

그 후 while문을 돌며 이분 탐색을 하면된다.

 

n = 6, times = [7, 10]

 

첫 번째 반복

middle값 => Math.floor((0+60)/2) => 30

people값 => Math.floor(30/7) + Math.floor(30/10) => 7

 

7은 우리가 가진 n값보다 크므로 right값을 middle - 1 값으로 지정해준다.

 

두 번째 반복

middle값 => Math.floor((0+29)/2)  => 14

people값 => Math.floor(14/7) + Math.floor(14/10) => 3

 

3은 우리가 가진 n값보다 현저히 작으므로 left값을 middle + 1로 바꿔준다.

 

세 번째 반복

middle값 => Math.floor((15+29)/2) => 22

people값 => Math.floor(22/7) + Math.floor(22/10) => 5

 

3은 우리가 가진 n값보다 현저히 작으므로 left값을 middle + 1로 바꿔준다.

 

.

.

.

 

정답이 구해질 때까지 반복하면 left값이 right값과 같아지거나 넘을 때 우리가 원하는 값(최소시간)을 구할 수 있다.

정답이 30이어도 되지만 left >= right까지 반복하므로 최소시간을 구할 수 있음