[프로그래머스] 입국심사 (JS) - binary search

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

코드

function solution(n, times) {
    times.sort((a,b)=>a-b);
    
    let left=1;
    let right=n*times[times.length-1];
    let answer = right;
    
    while(left<=right){
        let cnt=0;
        let mid = Math.floor((left+right)/2);
        for(time of times){
            cnt+=Math.floor(mid/time);
            if(cnt>=n){
                answer=Math.min(answer,mid);
                break;
            }
        }
        if(cnt>=n) right=mid-1;
        else left=mid+1;
    }
    return answer;
}

정리

이분탐색을 하기 위해서는 배열들이 정렬되어 있어야 한다.

times.sort((a,b)=>a-b);

 

mid값은 소수점을 갖지 않기 위해 Math.floor()를 해준다.

let mid = Math.floor((left+right)/2);

 

n과 가장 가까운 최솟값 cnt를 찾기 위해 다음과 같이 구현한다.

if(cnt>=n) right=mid-1;
else left=mid+1;

 

참조

https://velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level3-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC