입국심사 (Java)

📌 문제 설명

입국심사 - 프로그래머스

각 심사관이 한 명을 심사하는 데 걸리는 시간이 다를 때, 주어진 n명의 사람이 심사를 받는 최소 시간을 구하는 문제입니다.

---

💡 접근 방식

일반적으로 이분 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용합니다.
하지만 이 문제에서는 답이 될 수 있는 값(result)을 정해두고,
이 값이 가능한지 이분 탐색을 활용하여 판별합니다.

이러한 방법을 매개변수 탐색(Parametric Search)이라고 합니다.

---

🔹 매개변수 탐색이란?

매개변수 탐색이란, 답이 될 수 있는 값을 특정 범위에서 설정한 후, 이분 탐색을 통해 최적의 값을 찾는 알고리즘입니다.

✔ 이 문제에서는 최소 시간을 start, 최대 시간을 end로 설정한 후,
✔ 중간값(mid)을 result로 두고 심사가 가능한지 판단
✔ mid 시간이 충분하면, 더 적은 시간에서도 가능할지 확인 (end = mid)
✔ mid 시간이 부족하면, 더 많은 시간이 필요하므로 (start = mid + 1)

---

🔹 이분 탐색 과정

1. start는 0초, end는 최대 심사관이 한 명씩 심사하는 최악의 경우
   • 즉, end = 1,000,000,000,000,000,000L (최악의 경우 모든 사람이 가장 느린 심사관에게 심사받을 때)
2. mid = (start + end) / 2 를 설정하고,
   해당 시간 동안 몇 명을 심사할 수 있는지 계산
3. 만약 sum >= n (모든 사람을 심사 가능하면) → end = mid
4. 그렇지 않다면 → start = mid + 1
5. 이분 탐색이 끝난 후 end 값이 최소 시간이 됨.

---

📝 코드 구현

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long start = 0, end = 1_000_000_000_000_000_000L; // 최악의 경우 최대값 설정
        while (start < end) {
            long mid = (start + end) / 2; // 이분 탐색을 위한 중간값
            long sum = 0;

            // 현재 mid 시간 동안 처리할 수 있는 총 인원 계산
            for (int time : times) {
                sum += mid / time;
            }

            // 모든 인원을 처리할 수 있다면 시간을 줄여본다.
            if (sum >= n) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
}

---

🧐 코드 분석

변수	의미
start	최소 가능한 심사 시간 (초기값: 0)
end	최대 가능한 심사 시간 (10^18)
mid	현재 탐색하는 시간 (이분 탐색 중간값)
sum	mid 시간 동안 심사할 수 있는 총 인원

🔹 시간복잡도

• 이분 탐색의 시간 복잡도: O(log M), (M은 end 값, 약 10^18)
• 각 단계에서 심사관 수(k)만큼 반복: O(k)
• 총 시간복잡도: O(k log M)

---

🎯 예제 실행

입력 예시

int n = 6;
int[] times = {7, 10};

이분 탐색 과정

start	end	mid	sum (처리 가능 인원)	조정 방향
0	10^18	5 * 10^17	충분함	end = mid
0	5 * 10^17	2.5 * 10^17	충분함	end = mid
...	...	...	...	...
20	21	20	부족함	start = mid + 1
21	21	21	충분함	end = mid

✅ 결과: 28 (최소 28초가 필요)

---

🚀 결론 및 정리

🔹 핵심 개념

1. 이분 탐색을 활용한 "매개변수 탐색" 문제
2. 답이 될 수 있는 값을 기준으로 탐색
3. 이분 탐색을 활용해 최적의 최소 시간 찾기