프로그래머스: 입국심사(JAVA)

문제 요약

입국 심사를 기다리는 n명의 사람들이 있고, 여러 명의 심사관이 있습니다.
각 심사관은 사람 한 명을 심사하는 데 걸리는 시간이 모두 다릅니다.

모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구해야 합니다.

---

시간에 대한 이분 탐색

처음엔 사람을 기준으로 "누가 언제 어디로 가야 가장 빠를까?"라고 고민할 수 있지만,
그렇게 하면 너무 복잡하고 비효율적인 풀이가 됩니다.

이 문제는 시간을 기준으로 생각하면 매우 깔끔하게 풀 수 있습니다.

"어떤 시간 t가 주어졌을 때, 이 t 안에 n명 모두 심사를 받을 수 있는가?"

이 조건을 판단할 수 있다면, 우리는 이분 탐색으로 t의 최소값을 찾을 수 있습니다.

 

문제 정리

• 최소 시간 start = 1
• 최대 시간 end = 가장 느린 심사관 시간 × n
• mid = (start + end) / 2에서,
  • 모든 심사관이 mid 시간 동안 처리할 수 있는 사람 수의 합을 계산
  • 이 합이 n보다 크거나 같으면 → mid가 가능한 시간! 더 줄일 수 있는지 확인
  • 작으면 → 시간이 부족하므로 더 늘려야 함

---

Java 코드

class Solution {
    public long solution(int n, int[] times) {
        long start = 1;
        long end = (long) times[times.length - 1] * n;
        
        long answer = end;
        
        while (start <= end) {
            long mid = (start + end) / 2;
            
            long count = 0;
            for (int time : times) {
                count += mid / time;  // 이 심사관이 mid 시간 동안 몇 명 처리할 수 있는가
            }
            
            if (count >= n) {
                answer = mid;       // 가능한 시간, 줄여보자
                end = mid - 1;
            } else {
                start = mid + 1;    // 부족하니까 늘려야 함
            }
        }
        
        return answer;
    }
}

 

예시

n = 6;
times = [7, 10];

• 가능한 최소 시간: 28분
  • 7분 심사관은 28분 동안 4명
  • 10분 심사관은 28분 동안 2명
  • 총 6명 → 딱 맞음!

---

시간 복잡도

• log(최대 시간) ≒ log(10^18)
• 매 탐색마다 k명의 심사관을 순회 → O(k)
• 총 시간 복잡도: O(log(n × maxTime) × k)