이분탐색 / 3 / 입국심사

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다.

각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

 

처음에 모든 심사대는 비어있습니다.

한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.

가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.

하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

 

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데

걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때,

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

 

문제 풀이 방법

• 문제는 이분탐색 알고리즘을 이용해 모든 사람이 심사를 완료하는 최소 시간을 구하는 것이다.
• 우선 모든 사람이 검사를 받는 최대 시간은 가장 오래걸리는 시간 X 총 인원 이다. 최소 시간은 0으로 둔다.
• 이제 최대 최소 시간으로 이분 탐색을 하여 n명을 탐색 할 수 있는지 확인한다.
• 중간 값을 각 소요시간으로 나누면 각 소요시간 당 심사 가능 인원이 나와 이를 다 더해준 값을 총 인원과 비교
  peopleCount가 n이상이면 mid -1, peopleCount가 n미만이면 mid +1
  (±1을 해주는 이유는 최소 몇 분의 제한 시간을 설정해야 총 인원이 심사를 받을 수 있느냐를 구하기 때문이다.)
  (문제의 예제에서는 28과 29가 나올 수 있기에 가장 작은 수를 구하기 위함이다.)
• 비교를 하고 다음 이분탐색을 위해 중간 값을 다시 구해준다.

 

코드

function solution(n, times) {
    times.sort((a, b) => a - b);
    
    let min = 0;
    let max = n * times[times.length - 1];
    let mid = Math.floor((min + max) / 2);
    
    while(min <= max){
        const peopleCount = times.reduce((initial, cur) => initial + Math.floor(mid / cur), 0);
        
        if(peopleCount >= n){
            max = mid - 1;
        }
        else if(peopleCount < n){
            min = mid + 1;
        }
        mid = Math.floor((min + max) / 2);
    }
    return min;
}

 

진짜 처음보고 왜 이분탐색인지 몰랐지만 구글링을 해서

다른 사람이 작성한 코드를 이해하며 이분탐색을 사용해야 함을 깨달았다.

 

아직 많이 부족한것 같다.....

그러니 계속 공부하자.....ㅠ