programmers) 입국심사

프로그래머스 입국심사, 사람배정이 아닌 시간을 이분 탐색하기

이번에는 프로그래머스의 입국심사 문제를 풀어보았다.

👉프로그래머스 입국심사 문제

처음에는 꽤 어려웠다.

문제를 읽었을 때 자연스럽게 이렇게 생각했다.

각 사람을 어떤 심사관에게 배정해야 하지?
더 빠른 심사관에게 먼저 보내야 하나?
비어 있는 심사대가 있어도 기다렸다가 더 빨리 끝나는 심사대를 이용해야 하나?

하지만 이 문제는 사람을 심사관에게 직접 배정하는 문제가 아니었다.

핵심은 n명을 모두 심사할 수 있는 최소 시간을 구하는 것이었다.

---

문제 설명

입국심사를 기다리는 사람 수 n명이 있고, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 times 배열로 주어진다.

모든 사람이 심사를 받는 데 걸리는 최소 시간을 구해야 한다.

예를 들어:

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

7분이 걸리는 심사관과 10분이 걸리는 심사관이 있다.

6명을 모두 심사하는 최소 시간은 28분이다.

---

문제 유형 분류

이 문제는 이분 탐색 문제이다.

정확히는 정렬된 배열에서 특정 값을 찾는 일반적인 이분 탐색이 아니라,

정답이 될 수 있는 시간 범위를 이분 탐색하는 문제

이다.

이런 문제는 보통 아래와 같은 특징이 있다.

최소 시간을 구하라
최대 길이를 구하라
최소 비용을 구하라
어떤 값이 가능하거나 불가능한지 판단할 수 있다

입국심사에서는 다음 질문으로 바꿀 수 있다.

X분 안에 n명을 모두 심사할 수 있는가?

이 질문에 답할 수 있기 때문에 시간을 기준으로 이분 탐색을 할 수 있다.

---

처음 접근했던 방식

처음에는 사람을 심사관에게 직접 배정하려고 했다.

예를 들어:

1번 사람은 7분 심사관
2번 사람은 10분 심사관
3번 사람은 다시 7분 심사관

이런 식으로 생각했다.

또 times = [7, 10]이면 각각의 심사 종료 시간 배열을 만들어야 하나 고민했다.

7분 심사관 종료 시간
7, 14, 21, 28, 35, 42 ...

10분 심사관 종료 시간
10, 20, 30, 40, 50, 60 ...

두 배열을 합치면:

7, 10, 14, 20, 21, 28, 30 ...

6번째 사람이 끝나는 시간은 28분이므로 정답이 28이라는 것은 이해할 수 있다.

하지만 n이 매우 커지면 종료 시간을 하나씩 배열에 저장하는 방식은 사용할 수 없다.

즉, 이 문제는 종료 시간을 직접 나열하거나 사람을 배정하는 방식으로 풀면 안 된다.

---

핵심 사고 전환

이 문제에서 가장 중요한 것은 아래처럼 생각을 바꾸는 것이다.

사람을 심사관에게 어떻게 배정할까?

가 아니라,

mid분 안에 각 심사관은 몇 명을 처리할 수 있을까?

를 계산해야 한다.

예를 들어 mid = 28이라고 해보자.

7분 심사관
28 / 7 = 4명

10분 심사관
28 / 10 = 2명

그래서 총 처리 가능한 사람 수는:

4 + 2 = 6명

이다.

즉, 28분 안에 6명을 심사할 수 있다.

여기서 중요한 점은 누가 어떤 심사관에게 가는지 직접 배정하지 않았다는 것이다.

그냥 각 심사관이 28분 동안 처리할 수 있는 인원만 계산했다.

---

비어 있는 심사대가 있어도 기다릴 수 있다는 조건

문제 설명에는 비어 있는 심사대가 있어도 더 빨리 끝나는 심사대를 기다릴 수 있다는 내용이 나온다.

이 부분이 처음에 많이 헷갈렸다.

예를 들어 times = [7, 10], n = 6일 때를 생각해보자.

7분 심사관
0~7
7~14
14~21
21~28

10분 심사관
0~10
10~20
20~30

20분에 10분 심사대가 비어 있다.

하지만 마지막 사람이 바로 10분 심사대에 들어가면:

20~30

이 되어 전체 완료 시간이 30분이 된다.

반면 1분을 기다렸다가 21분에 비는 7분 심사대에 들어가면:

21~28

이 되어 전체 완료 시간이 28분이 된다.

그래서 빈 심사대가 있다고 무조건 바로 이용하는 것이 최적은 아니다.

하지만 이 대기 여부를 직접 코드로 구현할 필요는 없다.

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

이 계산 안에는 마지막 사람이 21분까지 기다렸다가 7분 심사대를 이용하는 경우까지 이미 포함되어 있다.

---

시간 범위 정하기

이분 탐색을 하려면 먼저 시간 범위를 정해야 한다.

최소 시간

가장 작은 시간 후보는 1분으로 둘 수 있다.

long left = 1;

정답이 0분일 수는 없기 때문이다.

---

최대 시간

최대 시간은 가장 빠른 심사관이 모든 사람을 혼자 심사하는 경우로 잡을 수 있다.

Arrays.sort(times);

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

예를 들어:

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

이면 정렬 후 가장 빠른 심사 시간은 7분이다.

7분 심사관이 혼자 6명을 심사하면
7 * 6 = 42분

따라서 정답은 무조건 1분부터 42분 사이에 있다.

left = 1
right = 42

---

mid 시간으로 가능한지 확인하기

이분 탐색에서는 현재 범위의 중간 시간을 구한다.

long mid = left + (right - left) / 2;

여기서 mid는 다음 질문의 기준 시간이다.

mid분 안에 n명을 모두 심사할 수 있는가?

각 심사관이 mid분 동안 처리할 수 있는 사람 수를 모두 더한다.

long student = 0;

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

예를 들어 mid = 21이면:

21 / 7 = 3명
21 / 10 = 2명

총 5명

6명보다 적으므로 21분은 부족하다.

student < n

이 경우 시간을 더 늘려야 한다.

left = mid + 1;

반대로 mid = 32이면:

32 / 7 = 4명
32 / 10 = 3명

총 7명

6명 이상 심사할 수 있으므로 32분은 가능하다.

student >= n

하지만 우리는 최소 시간을 찾아야 하므로 더 작은 시간도 가능한지 확인해야 한다.

min = mid;
right = mid - 1;

---

내가 최종적으로 작성한 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);

        long left = 1;
        long right = (long) times[0] * n;
        long min = Long.MAX_VALUE;

        while (right >= left) {
            long student = 0;
            long mid = left + (right - left) / 2;

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

            if (student >= n) {
                right = mid - 1;
                min = mid;
            } else if (student < n) {
                left = mid + 1;
            }
        }

        return min;
    }
}

---

코드 흐름 정리

전체 흐름은 아래와 같다.

1. 심사 시간을 정렬한다.
2. left는 1분으로 설정한다.
3. right는 가장 빠른 심사관이 n명을 모두 심사하는 시간으로 설정한다.
4. mid 시간을 구한다.
5. mid분 동안 처리 가능한 사람 수를 계산한다.
6. n명 이상 처리 가능하면:
   - 현재 mid는 정답 후보
   - 더 작은 시간을 확인하기 위해 right를 줄인다.
7. n명보다 적게 처리 가능하면:
   - 시간이 부족하므로 left를 늘린다.

---

처음에 실수했던 부분

1. 사람을 직접 배정하려고 했던 점

처음에는 사람을 어떤 심사관에게 보내야 하는지 고민했다.

하지만 이 문제는 배정 문제가 아니라 시간에 대한 가능 여부를 판단하는 문제였다.

X분 안에 n명을 심사할 수 있는가?

이 질문으로 바꾸는 것이 핵심이었다.

---

2. 종료 시간 배열을 만들려고 했던 점

처음에는 7의 배수, 10의 배수처럼 각 심사관의 종료 시간을 배열로 만들고 비교하려고 했다.

7, 14, 21, 28 ...
10, 20, 30, 40 ...

작은 예제에서는 가능해 보이지만, n이 크면 종료 시간 배열을 전부 만들 수 없다.

그래서 직접 나열하지 않고 아래처럼 계산해야 한다.

student += mid / time;

---

3. mid 계산식

처음에는 괄호 위치를 잘못 작성했다.

잘못된 코드:

mid = (left + (right - left)) / 2;

이 식은 정리하면 사실상 아래와 비슷하다.

mid = right / 2;

그래서 left와 right의 가운데를 구하지 못한다.

올바른 코드는 아래와 같다.

mid = left + (right - left) / 2;

---

4. student를 반복마다 초기화해야 한다

student는 현재 mid 시간 안에 처리 가능한 사람 수이다.

따라서 mid가 바뀔 때마다 다시 0부터 계산해야 한다.

while (right >= left) {
    long student = 0;
    ...
}

만약 student를 while문 밖에 두면 이전 mid에서 계산한 값이 계속 누적되어 잘못된 결과가 나온다.

---

시간 복잡도

심사 시간을 정렬하는 데:

O(T log T)

이분 탐색은 시간 범위를 절반씩 줄이므로:

O(log(maxTime * n))

각 이분 탐색 단계마다 모든 심사관을 확인하므로:

O(T)

전체 시간복잡도는 다음과 같다.

O(T log T + T log(maxTime * n))

여기서 T는 심사관 수이다.

---

공간 복잡도

추가 배열이나 리스트를 만들지 않고 변수만 사용했다.

공간복잡도: O(1)

정렬 내부에서 사용하는 공간은 제외하고 생각했다.

---

이번 문제에서 배운 점

이번 문제는 이분 탐색이 정렬된 배열에서만 사용하는 알고리즘이 아니라는 것을 알려준 문제였다.

정답이 될 수 있는 시간 범위를 줄여나가면서 최소값을 찾을 수도 있다.

앞으로 비슷한 문제를 만나면 아래 질문을 먼저 해봐야겠다.

구해야 하는 값이 숫자인가?
최소값 또는 최대값을 구하는가?
어떤 값 X를 정했을 때 가능/불가능을 판단할 수 있는가?
X가 커질수록 가능해지는가?

입국심사 문제는 모두 만족한다.

구해야 하는 값: 최소 시간
판단 기준: X분 안에 n명 심사 가능 여부
시간이 커질수록: 처리 가능한 사람 수 증가

그래서 이분 탐색으로 풀 수 있었다.

---

셀프 체크

왜 못 풀었는가?

사람을 심사관에게 직접 배정하는 문제라고 생각해서 접근이 복잡해졌다.

시간이 부족했는가?

시간보다 문제를 보는 관점이 바로 떠오르지 않았던 것이 더 컸다.

문제 해석을 잘못했는가?

문제 자체는 이해했지만, 구해야 하는 값이 “n명을 심사할 수 있는 최소 시간”이라는 점에서 출발하지 못했다.

자료구조 선택을 잘못했는가?

처음에는 각 심사관의 종료 시간을 배열로 만들려고 했지만, 입력이 커지면 사용할 수 없는 방식이었다.

구현 실수가 있었는가?

mid 계산식의 괄호 위치를 잘못 작성했고, student를 반복마다 초기화해야 한다는 점도 놓쳤다.

시간 복잡도 판단을 잘못했는가?

종료 시간을 하나씩 나열하는 방식은 n이 커지면 너무 많은 시간과 공간이 필요하다.

이분 탐색을 사용하면 시간 범위를 절반씩 줄여가며 최소 시간을 구할 수 있다.

---

마무리

입국심사 문제의 핵심은 이 한 문장으로 정리할 수 있다.

사람을 심사관에게 직접 배정하지 말고,
X분 안에 몇 명을 심사할 수 있는지 계산하자.

이번 문제를 통해 “정답을 이분 탐색하는 문제”의 사고방식을 조금 더 이해할 수 있었다.