문제 29 - 입국 심사 (Python)

프로그래머스

입국심사는 모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구하는 문제입니다. 핵심은 사람을 심사대에 직접 배정하는 것이 아니라, 특정 시간 안에 n명 이상 처리할 수 있는지를 기준으로 시간 범위를 이분 탐색하는 것입니다.

---

1.  나의 풀이

def solution(n, times):
    min_time = 1
    max_time = min(times) * n
    mid_time = max_time // 2

    while min_time < max_time:
        possible_number = 0
        for t in times:
            possible_number += mid_time // t

        if possible_number >= n:
            max_time = mid_time
        else:
            min_time = mid_time + 1
        mid_time = min_time + (max_time - min_time) // 2

    return mid_time

---

2.  오늘 배운 점 및 복기 노트

탐색 대상은 사람이 아니라 시간입니다.

처음에는 각 사람이 어느 심사대로 가야 하는지를 생각하기 쉽습니다. 하지만 이 문제는 배정 순서를 직접 시뮬레이션하는 문제가 아닙니다. 특정 시간 mid_time 안에 몇 명까지 심사할 수 있는지를 계산하고, 그 시간이 가능한지 판단하는 문제입니다.

---

처리 가능 인원 계산 방식

어떤 시간 mid_time이 주어졌을 때, 각 심사대가 처리할 수 있는 인원은 다음과 같습니다.

mid_time // t

 

예를 들어 mid_time = 28, times = [7, 10]이면 다음과 같습니다.

28 // 7 = 4
28 // 10 = 2

총 6명 처리 가능

따라서 28분은 6명을 처리할 수 있는 가능한 시간입니다.

---

가능하면 시간을 줄이고, 불가능하면 시간을 늘립니다.

mid_time 안에 n명 이상 처리할 수 있다면 그 시간은 가능한 시간입니다. 하지만 최소 시간을 구해야 하므로 더 작은 시간도 가능한지 왼쪽 범위를 탐색해야 합니다.

max_time = mid_time

반대로 mid_time 안에 n명을 처리할 수 없다면 mid_time 이하의 시간은 전부 불가능합니다. 따라서 다음 탐색은 mid_time + 1부터 시작해야 합니다.

min_time = mid_time + 1

---

possible_number == n은 정답 확정 조건이 아닙니다.

처음 시도한 코드에서는 다음과 같은 조건을 사용했습니다.

if possible_number <= n:
    min_time = mid_time

if possible_number >= n:
    max_time = mid_time

이 코드는 possible_number == n일 때 두 조건이 모두 실행됩니다. 즉, min_time과 max_time이 동시에 mid_time으로 바뀌면서 탐색 범위가 잘못 좁아질 수 있습니다.

하지만 possible_number == n이라고 해서 그 시간이 최소라는 보장은 없습니다.

예를 들어 입출력 예시에서는 다음이 모두 가능합니다.

28분 → 6명 처리 가능
29분 → 6명 처리 가능

따라서 29분도 처리 가능 인원이 정확히 6명이지만 정답은 아닙니다. 더 작은 28분도 가능하기 때문입니다.

이 문제에서 중요한 조건은 정확히 n명 처리 가능이 아니라 n명 이상 처리 가능입니다.

---

불가능한 mid_time은 다시 탐색 범위에 포함하지 않습니다.

처음 시도한 코드에서는 불가능한 경우에도 다음과 같이 처리했습니다.

min_time = mid_time

이렇게 하면 범위가 줄지 않는 경우가 생길 수 있습니다.

예를 들어 다음 상황을 생각할 수 있습니다.

min_time = 27
max_time = 28
mid_time = 27

27분이 불가능하다면 다음에는 반드시 28분부터 봐야 합니다. 따라서 다음처럼 작성해야 합니다.

min_time = mid_time + 1

이 부분을 놓치면 같은 mid_time이 반복되어 무한 루프가 발생할 수 있습니다.

---

mid_time을 갱신하는 위치

나의 풀이에서는 mid_time을 반복문 마지막에 다시 계산했습니다.

mid_time = min_time + (max_time - min_time) // 2

일반적으로는 반복문 안의 시작 부분에서 mid_time을 계산하는 형태도 많이 사용합니다. 하지만 현재 코드처럼 범위를 갱신한 뒤 마지막에 다음 mid_time을 계산하는 방식도 같은 이분 탐색 흐름입니다.

핵심은 min_time과 max_time이 갱신된 뒤, 그 범위의 중간값을 다시 검사한다는 점입니다.

---

파라메트릭 서치 구조

이 문제는 파라메트릭 서치 문제입니다. 파라메트릭 서치는 정답 후보 값(여기서는 시간)에 대해 가능 여부를 판단할 수 있고, 그 가능 여부가 한 방향으로 정렬되어 있을 때 사용하는 이분 탐색입니다.

입국심사 문제에서는 시간이 커질수록 처리 가능한 인원이 줄어들지 않습니다.

불가능 불가능 불가능 가능 가능 가능
                  ↑
          처음 가능해지는 시간

우리가 찾아야 하는 값은 처음으로 n명 이상 처리할 수 있는 시간입니다.

---

3. 프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

입력 크기를 보고 완전 탐색을 배제합니다.

이 문제는 n이 최대 1,000,000,000까지 주어집니다. 사람을 한 명씩 심사대에 배정하는 방식이나 시간 흐름을 직접 시뮬레이션하는 방식은 입력 크기상 적합하지 않습니다.

입력 크기가 매우 크고, 정답 후보 범위에서 가능 여부를 판단할 수 있다면 이분 탐색 또는 파라메트릭 서치를 먼저 의심해야 합니다.

---

비어 있는 심사대를 직접 관리하지 않습니다.

문제 설명에는 비어 있는 심사대, 더 빨리 끝나는 심사대 등의 표현이 나옵니다. 이 때문에 우선순위 큐나 스케줄링을 떠올릴 수 있습니다.

하지만 이 문제에서 필요한 것은 실제 배정 과정이 아니라 전체 시간이 충분한지 여부입니다. 특정 시간 안에 각 심사대가 몇 명을 처리할 수 있는지만 계산하면 됩니다.

---

정답의 최대 범위를 안전하게 잡습니다.

최소 시간의 오른쪽 끝은 다음처럼 잡을 수 있습니다.

max_time = min(times) * n

가장 빠른 심사관 한 명이 모든 사람을 처리한다고 가정한 시간입니다. 실제로는 여러 심사관이 동시에 처리하므로 정답은 이 값보다 클 수 없습니다.

---

>= n을 기준으로 최소 가능 시간을 찾습니다.

이 문제는 정확히 n명을 처리하는 시간을 찾는 문제가 아닙니다. 특정 시간 안에 n명 이상 처리할 수 있으면 가능한 시간입니다.

따라서 조건은 다음처럼 작성해야 합니다.

if possible_number >= n:
    max_time = mid_time
else:
    min_time = mid_time + 1

이 조건을 기준으로 가능한 시간 중 가장 작은 값을 찾는 것이 핵심입니다.