[알고리즘 문제] 이분 탐색 - 프로그래머스 입국심사(level 3)

문제 이해

심사관마다 한 사람을 처리하는 시간이 다르고 모든 심사대는 처음에 비어 있습니다. 기다리는 n명이 어떤 심사대를 선택하든 상관없이, 전원이 심사를 마치는 데 필요한 최소 시간을 구해야 합니다.

예를 들어 n = 6, times = [7, 10]이면 7분 심사대는 28분 동안 4명, 10분 심사대는 2명을 처리할 수 있으므로 답은 28분입니다.

시뮬레이션이 어려운 이유

가장 직관적인 방법은 각 심사대가 다음에 비는 시간을 관리하며 사람을 한 명씩 배치하는 것입니다. 하지만 사람 수가 최대 10억 명이므로 한 사람마다 작업하는 방식은 입력 상한에서 사용할 수 없습니다.

답을 만드는 과정을 직접 재현하기보다, 어떤 시간 T가 답으로 충분한지 빠르게 판정할 수 있는지를 먼저 생각해야 합니다.

시간을 결정 문제로 바꾸기

한 사람을 심사하는 데 time분이 걸리는 심사관은 T분 동안 T / time명을 처리할 수 있습니다. 정수 나눗셈을 사용하는 이유는 해당 시간 안에 끝난 심사만 세어야 하기 때문입니다.

processed(T) = T / times[0]
             + T / times[1]
             + ...

processed(T) >= n 이면 T분 안에 모두 심사 가능

시간이 늘면 처리 가능한 사람 수는 줄지 않습니다. 따라서 어떤 시점 전까지는 불가능하고, 그 시점부터는 계속 가능합니다.

시간:  0 ... 27 | 28 ...
판정: 불가능     | 가능

이처럼 판정 결과가 한 번만 바뀌므로 이분 탐색으로 최초의 가능한 시간을 찾을 수 있습니다.

탐색 범위 정하기

최소 시간은 아무도 심사하지 않은 0분을 하한으로 둘 수 있습니다.

left = 0

상한은 가장 빠른 심사관이 n명을 혼자 처리하는 시간입니다. 실제로는 다른 심사관도 함께 일하므로 정답은 반드시 이 값 이하입니다.

right = min(times) * n

times를 오름차순 정렬하면 times[0]으로 가장 빠른 심사 시간을 얻을 수 있습니다.

가능한 첫 시간을 찾기

left와 right를 모두 정답 후보가 될 수 있는 닫힌 범위로 관리합니다. 중간 시간에 n명 이상 처리할 수 있다면 그 시간도 답 후보이므로 right = mid로 줄입니다.

while (left < right) {
    long long mid = left + (right - left) / 2;
    long long count = 처리 가능한 사람 수;

    if (count >= n) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

처리할 수 없다면 mid는 정답이 아니므로 제외하고 left = mid + 1로 이동합니다. 반복이 끝나 left == right가 되면 두 값이 가리키는 위치가 최초의 가능한 시간입니다.

예제로 따라가기

n = 6, times = [7, 10]이면 탐색 범위는 0부터 7 × 6 = 42까지입니다.

mid	처리 인원	판정	다음 범위
21	21 / 7 + 21 / 10 = 5	불가능	[22, 42]
32	32 / 7 + 32 / 10 = 7	가능	[22, 32]
27	27 / 7 + 27 / 10 = 5	불가능	[28, 32]
30	30 / 7 + 30 / 10 = 7	가능	[28, 30]
29	29 / 7 + 29 / 10 = 6	가능	[28, 29]
28	28 / 7 + 28 / 10 = 6	가능	[28, 28]

27분에는 5명만 처리할 수 있지만 28분에는 6명을 처리할 수 있으므로 최소 시간은 28분입니다.

절반만 통과한 이유

처음 작성한 코드에서는 반환형만 long long으로 두고 다음처럼 상한을 계산했습니다.

long long right = times[0] * n;

대입받는 변수가 long long이어도 곱셈의 두 피연산자가 모두 int이면 곱셈부터 int로 수행됩니다. 제한값에서는 최대 1018까지 필요하므로 중간 결과가 먼저 오버플로한 뒤 잘못된 값이 저장될 수 있습니다.

long long right = static_cast<long long>(times[0])
                * static_cast<long long>(n);

곱셈 전에 피연산자를 long long으로 변환해야 실제 연산도 64비트 정수로 수행됩니다.

최종 코드

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());

    long long left = 0;
    long long right = static_cast<long long>(times[0])
                    * static_cast<long long>(n);

    while (left < right) {
        long long mid = left + (right - left) / 2;
        long long count = 0;

        for (int time : times) {
            count += mid / time;
        }

        if (count >= n) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

mid = left + (right - left) / 2 형태를 사용하면 left + right를 먼저 더할 때 생길 수 있는 오버플로도 피할 수 있습니다.

복잡도와 주의점

• 시간복잡도는 O(M log(N × T))
• 심사관 수를 M, 가장 빠른 심사 시간을 T라 하면 각 이분 탐색 단계에서 심사관을 한 번씩 순회합니다. 정렬의 O(M log M)도 필요합니다.
• 공간복잡도는 O(1)
• 정렬 구현의 내부 공간을 제외하면 탐색 경계와 처리 인원만 저장합니다.
• 값의 범위를 먼저 계산한다
• 정답과 상한이 최대 1018이므로 시간 관련 변수는 long long이어야 합니다.
• 가능한 경우에도 mid를 보존한다
• 최솟값을 찾으므로 가능한 mid 자체가 정답일 수 있습니다. 따라서 right = mid - 1이 아니라 right = mid를 사용합니다.

정리

• 최대 10억 명을 한 명씩 배치하는 시뮬레이션은 피한다.
• T분 동안 처리 가능한 인원은 각 심사대의 T / time을 더해 구한다.
• 시간이 늘수록 가능 여부가 불가능에서 가능으로 한 번만 바뀌므로 이분 탐색을 적용한다.
• 가장 빠른 심사관이 모두 처리하는 시간을 안전한 상한으로 사용한다.
• 큰 수의 곱셈은 연산 전에 long long으로 형변환해야 한다.

이번 문제에서는 대상을 직접 배치하는 대신 답의 후보인 시간을 탐색하는 관점 전환이 핵심이었습니다. 알고리즘이 맞아도 자료형 변환 시점 때문에 실패할 수 있다는 점까지 함께 확인했습니다.