프로그래머스 알고리즘 고득점 Kit - [Lv.3] 입국심사 (Java)

문제 출처 - 링크

알고리즘 분류

• 이분탐색

📋 문제 요약 설명

• 각 입국 심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다.
• 처음에 모든 심사대는 비어있다.
• 한 심사대에서는 동시에 한 명만 심사를 할 수 있다.
• 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다.
• 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다.
• 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 구하라

💡 알고리즘 설계 / 접근 방법

1. 시간을 가지고 이분 탐색을 사용한다.
2. 시간 배열에서 가장 작은 값과 가장 큰 값에 통과해야 할 인원수를 곱해서 최소 시간과 최대 시간을 구한다.
3. 최소 시간과 최대 시간의 중간 값으로 통과가 가능한 인원을 계산한다.
4. 통과 가능한 인원이 통과해야 할 인원이 될 때까지 최소 시간과 최대 시간의 범위를 조정한다.

✅ 풀이

시간 복잡도 → O(m × log T)

• m = 심사관 수, T = 최대 가능한 시간 ≈ n × 최장 심사 시간

1. 정렬 : O(m log m)
2. 전체 이분 탐색 : O(m × log(max_time))
   • 이분 탐색 반복 횟수 : O(log(max_time))
   • 각 이분 탐색 내에서 반복 : O(m)

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);        
        long minTime = (long)times[0]; // 가능한 최소 시간 (가장 빠른 심사관이 1명 심사하는 시간)
        long maxTime = (long)times[times.length-1] * n; // 가능한 최대 시간 (가장 느린 심사관이 모든 사람을 다 심사하는 최악의 경우)
        
        while (minTime <= maxTime) {
            long mid = (minTime + maxTime) / 2; // 이분 탐색의 중간 시간
            long pass = 0; // 입국심사를 통과한 인원

            // mid 시간 동안 처리 가능한 인원 계산
            for (int time : times) {
                pass += mid / time; // 해당 시간 내에 몇 명을 심사 가능한지 누적 계산
                if (pass >= n) 
                    break; // 통과 인원이 n명을 초과하면 더 계산할 필요 없음
            }

            if (pass >= n) { // 통과 가능한 인원이 통과를 기다리는 사람보다 많아지면
                answer = mid; // 가능한 시간 저장
                maxTime = mid - 1; // 더 작은 시간을 탐색하기 위해 최대 시간 범위를 줄임
            } else { // 통과 가능한 인원이 부족하므로
                minTime = mid + 1; // 시간 부족이기에 최소 시간 범위를 늘림
            }
        }

        return answer;
    }
}