[JavaScript] 프로그래머스 - 입국심사

[문제]

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

프로그래머스

 

[풀이]

이분탐색을 이용하여 문제를 풀이하였습니다.

 

예제 처럼 n이 6이고, time가 [7, 10] 이라면, 최대 심사 시간은 10*6 = 60분이됩니다.

 

최대 심사 시간 60을 기준으로 승객을 심사한다면 심사 가능 승객은 아래와 같습니다.

60 / 7 = 8명 + 60 / 10 = 10명 = 18명

 

하지만, 최소 시간으로 6명의 승객을 모두 심사해야 하므로, left = 1, right = 60으로 이분탐색을 진행합니다.

 

mid = (1 + 60)/2 = 30으로 시작하여 아래와 같이 이분탐색을 진행합니다.

• mid시간 기준으로 심사 가능 승객이 6보다 작다면, left = mid + 1로 갱신
• mid시간 기준으로 심사 가능 승객이 6보다 크거나 같다면, right = mid - 1로 갱신

따라서 최종적으로 left에 최소 시간이 저장되게 되고, 총 28분으로 모든 승객을 심사할 수 있습니다.

 

[코드]

function solution(n, times) {
    var answer = 0;
    times.sort((a, b) => a - b);
    
    const max = times[times.length -1]*n;
    
    let left = 1;
    let right = max;
    
    while(left <= right) {
        let mid = Math.floor((left + right)/2);
        
        let count = 0;
        for(let i=0;i<times.length;i++) {
            count += Math.floor(mid/times[i]);
        }
        
        if(count >= n) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    answer = left;
    
    return answer;
}