[프로그래머스 Level 3] 입국심사 (JS)

입국심사 문제 해결하기: 이분 탐색을 활용한 최적화

 

 

 

 

입국심사를 기다리는 많은 사람들이 있을 때, 각 심사대마다 심사를 진행하는 데 걸리는 시간이 다를 수 있다.

이러한 상황에서 모든 사람이 심사를 받는 데 걸리는 시간을 최소화하려면 어떻게 해야 할까?

이 문제는 효율적인 탐색 방법인 이분 탐색을 이용해 해결할 수 있다.

---

1. 문제 정의

입국심사를 기다리는 사람 수 n명과 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 주어진다. 모든 사람들이 심사를 완료하는 데 걸리는 최소 시간을 구하는 것이 목표이다.

제한사항:

• 심사 인원: 1명 이상 1,000,000,000명 이하
• 심사 시간: 1분 이상 1,000,000,000분 이하
• 심사관 수: 1명 이상 100,000명 이하

(+ 이렇게 천문학적인 숫자가 나오면 이분탐색을 해야한다고 짐작을 해야한다고 한다..)

 

 

2. 문제 해결을 위한 접근

이 문제는 이분 탐색을 사용해서 해결할 수 있다.

1. 심사대에서 최소, 최대 시간을 설정
   각 심사관의 처리 속도에 따라 모든 사람이 심사를 받는 데 걸리는 최소 및 최대 시간을 설정합니다. 
   • 최소 시간: lo = 0
     • (최소 시간은 사실 1이겠지만 모든 구간을 포함하기 위해 이렇게 설정한다.)
   • 최대 시간: hi = n * 가장 느린 심사관의 심사 시간 + 1
     • (이 부분도 모든 구간을 포함하기 위해 +1을 해준다)
2. 이분 탐색을 통해 중간 값을 탐색
   이분 탐색을 통해 시간 mid를 설정하고, 그 시간 안에 각 심사관들이 처리할 수 있는 인원을 계산한다. 
   • 각 심사관이 mid 시간 동안 처리할 수 있는 사람 수는 Math.floor(mid / 심사관의 시간) 이다.
   • 모든 심사관들이 처리한 인원 수가 n명 이상이면, 시간이 충분하다는 뜻이므로 시간을 줄이기 위해 hi 값을 줄이고, 그렇지 않으면 lo 값을 늘려준다.
3. 시간을 최소화
   이 과정을 반복하며, 모든 사람이 심사를 받는 데 걸리는 최소 시간을 탐색합니다.

 

3. 코드 구현

function solution(n, times) {
    times.sort((a,b) => a-b); // 심사 시간을 오름차순으로 정렬

    let lo = 1;
    let hi = n * times[times.length -1] + 1; // 최대 시간
    let answer = hi;

    while (lo+1 < hi) {
        let mid = Math.floor((lo + hi) / 2); // 중간값 설정
        
        let count = 0;
        times.forEach(time => {
            count += Math.floor(mid / time); // mid 시간 동안 처리 가능한 사람 수
            
             // 만약 모든 수가 n 보다 크면 
            if(count >= n) {
                answer = Math.min(mid, answer); // 최솟값 구하기
                return;
            };
        });

        if (count >= n) hi = mid; 
        else lo = mid; 
    }

    return answer;
}

 

 

4. 결론

이 문제는 각 심사관이 처리할 수 있는 사람 수를 계산하고, 이를 바탕으로 필요한 시간을 최소화하는 최적화 문제 였다.
효율적인 탐색 방법인 이분 탐색을 활용하여 문제를 해결할 수 있었고, 시간 복잡도는 O(log(n) * 심사관 수) 이다.