프로그래머스의 '입국심사' 문제는 탐색 범위가 무려 10억 명, 심사 시간은 10억 분에 달하는 전형적인 이분 탐색(Binary Search) 문제입니다.
1. 핵심 아이디어: "관점의 전환"
이 문제의 핵심은 '어떻게 사람을 배분할까?'가 아니라, **'특정 시간 $T$가 주어졌을 때, 모든 심사관이 총 몇 명을 심사할 수 있는가?'**로 질문을 바꾸는 것입니다.
- 결정 문제로 변환: "모든 사람을 심사하는 데 $T$분만큼 걸리는가?"라는 질문에 대해 YES/NO를 판단합니다.
- 계산식: $T$분 동안 한 심사관이 심사할 수 있는 인원수는 $\lfloor T / \text{심사시간} \rfloor$입니다. 모든 심사관의 처리량을 합친 값이 $n$보다 크거나 같다면, 그 시간 내에 심사가 가능하다는 뜻입니다.
- 이분 탐색 범위:
- 최솟값 (left): 1분
- 최댓값 (right): 가장 느린 심사관이 모든 사람을 처리할 때 걸리는 시간 ($n \times \text{max(times)}$)
2. 알고리즘 시각화
이분 탐색을 통해 최적의 시간을 찾아가는 과정입니다.
3. 파이썬 정답 코드 (상세 주석 포함)
Python
def solution(n, times):
# 이분 탐색을 위한 시작점과 끝점 설정
# left는 최소 1분, right는 가장 느린 심사관이 모두 처리하는 최악의 경우
left = 1
right = max(times) * n
# 최종 정답을 저장할 변수 (최댓값으로 초기화)
answer = right
while left <= right:
# 중간값(시간) 설정
mid = (left + right) // 2
# mid분 동안 모든 심사관이 심사할 수 있는 총 인원수 계산
people = 0
for time in times:
# 각 심사관당 (mid // 심사시간)명만큼 처리 가능
people += mid // time
# 이미 n명을 넘었다면 더 계산할 필요 없이 중단 (최적화)
if people >= n:
break
# 만약 mid분 동안 n명 이상 심사할 수 있다면
if people >= n:
# 현재 시간이 답이 될 수 있으므로 저장
answer = mid
# 더 짧은 시간 중에도 가능한지 확인하기 위해 범위를 왼쪽으로 좁힘
right = mid - 1
# n명보다 적게 심사한다면 시간이 부족한 것이므로
else:
# 범위를 오른쪽으로 좁혀 시간을 늘림
left = mid + 1
return answer
4. 왜 이분 탐색인가요?
- 데이터 범위: $n$이 10억이기 때문에 일반적인 반복문이나 그리디로는 절대 풀 수 없습니다.
- 로그 시간 복잡도: 이분 탐색의 시간 복잡도는 $O(\log(\text{최악의 시간}) \times \text{심사관 수})$입니다. $10^9$을 로그로 계산하면 약 30 정도밖에 되지 않아 매우 효율적입니다.
- 결정 문제: '시간'이라는 연속적인 값에서 최솟값을 찾는 문제에 매우 적합합니다.
이분 탐색 문제를 풀 때 가장 어려운 점은 **'무엇을 이분 탐색의 대상으로 잡을 것인가'**를 결정하는 것입니다. 이 문제처럼 결과값이 매우 크고 규칙성이 있다면 '시간'이나 '거리'를 대상으로 삼아보세요.