[99클럽 코테 스터디 19일차 TIL] 이분 탐색으로 입국 심사 문제 풀이

문제

프로그래머스 - 입국 심사 문제를 보고 풀이한 내용이다.

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

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

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

풀이

이분 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다. 따라서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근하는 것이 좋다. 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많기 때문이다.

따라서 위 문제에서도 제한사항을 살펴보면 입국심사를 기다리는 사람은 1명 이상 10억 명 이하이고, 심사관이 1명 이상 10만 명, 각 심사관이 한 명을 심사하는데 걸리는 시간이 1분 이상 10억 분 이하이기 때문에 다른 방법을 시도해보기에 앞서 이분 탐색을 고려해볼만 하다.

이분 탐색(Binary Search)?

이분 탐색은 이전에 공부하면서 정리해둔 부분이 있어서 참고하면서 풀었다. 많은 문제가 아래와 같은 틀을 따른다.

따라서, 이분 탐색을 사용하면서 이 문제를 풀기 위해 떠올릴 수 있는 로직은 다음과 같다.

0. 심사하는데 걸리는 시간 오름차순으로 정렬
1. 최소 시간과 최대 시간을 설정(1 ~ 가장 오래 걸리는 심사대에서 모든 인원이 심사받는 시간)
2. 최소 시간에서 최대 시간까지를 반으로 쪼개 이분 탐색
3. 모든 심사대에서 처리한 사람의 수의 합이 전체 인원 수보다 작으면 더 큰 시간에 대한 탐색
4. 모든 심사대에서 처리한 사람의 수의 합이 전체 인원 수보다 크거나 같으면 최소 시간을 갱신하고 더 작은 시간에 대한 탐색
5. 최소 시간과 최대 시간이 같아질 때까지 반복
6. 최종적으로 최소 시간 반환

이대로 코드로 옮겨보자.

정답 코드

public long solution(int n, int[] times) {
        // 심사대에서 심사하는데 걸리는 시간을 오름차순으로 정렬합니다.
        Arrays.sort(times);

        // 이분 탐색을 위한 left, right 설정
        long left = 1; // 최소 시간은 1분
        long right = (long) times[times.length - 1] * n; // 최대 시간은 가장 오래 걸리는 심사대에서 모든 사람을 심사하는 시간

        long answer = Long.MAX_VALUE;

        // 이분 탐색 시작
        while (left <= right) {
            long mid = (left + right) / 2; // 중간값 계산
            long total = 0; // mid 시간 동안 심사 가능한 총 인원 수

            // 각 심사대에서 mid 시간 동안 처리할 수 있는 인원 수 계산
            for (int time : times) {
                total += mid / time;
            }

            // 심사 가능한 총 인원 수가 목표 인원보다 크거나 같은 경우
            if (total >= n) {
                // 최소 시간 갱신하고, 더 작은 시간에 대한 탐색을 진행
                answer = Math.min(answer, mid);
                right = mid - 1;
            } else { // 심사 가능한 총 인원 수가 목표 인원보다 작은 경우
                // 더 큰 시간에 대한 탐색을 진행
                left = mid + 1;
            }
        }

        // 최소 시간 반환
        return answer;
    }