입국심사

프로그래머스의 입국심사 문제를 함께 풀어보도록 하겠습니다.

문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

예제

Input:
  n: 6
  times: [7, 10]
Output: 28

풀이 1

주어진 예제의 결과로 왜 28분이 심사를 받는 데 걸리는 시간의 최소값인지를 먼저 생각해 볼까요?

심사관이 2명이므로 모든 사람은 2개 선택지가 있습니다. 심사관 A에게 가거나 심사관 B한테 가는 것이지요.

• 1 번째 사람은 심사관 A로 보냅니다. 심사관 A에게 가면 0 + 7 = 7분에 심사가 끝나고, 심사관 B에게 가면 0 + 10 = 10분에 끝나기 때문입니다.
• 2 번째 사람은 심사관 B로 보냅니다. 심사관 A에게 가면 7 + 7 = 14분에 심사가 끝나고, 심사관 B에게 가면 0 + 10 = 10분에 끝나기 때문입니다.
• 3 번째 사람은 심사관 A로 보냅니다. 심사관 A에게 가면 7 + 7 = 14분에 심사가 끝나고, 심사관 B에게 가면 10 + 10 = 20분에 끝나기 때문입니다.
• 4 번째 사람은 심사관 B로 보냅니다. 심사관 A에게 가면 14 + 7 = 21분에 심사가 끝나고, 심사관 B에게 가면 10 + 10 = 20분에 끝나니 때문입니다.
• 5 번째 사람은 심사관 A로 보냅니다. 심사관 A에게 가면 14 + 7 = 21분에 심사가 끝나고, 심사관 B에게 가면 20 + 10 = 30분에 끝나니 때문입니다.
• 6 번째 사람은 심사관 B로 보냅니다. 심사관 A에게 가면 21 + 7 = 28분에 심사가 끝나고, 심사관 B에게 가면 20 + 10 = 30분에 끝나니 때문입니다.

정리해보면, 아래와 같이 시각화가 되겠네요.

👮A(7분) : 🚶1(7분), 🚶3(14분), 🚶5(21분), 🚶6(28분)
👮B(10분): 🚶2(10분), 🚶4(20분)

마지막 6번째 사람의 선택이 흥미로워요. 심사관 B가 20분에 먼저 비지만, 1분 기다렸다가 21분에 심사관 A에게 갑니다. 왜냐하면 심사관 A에게 가면 28분에 심사를 끝낼 수 있지만, 심사관 B에게 가면 30분에 심사가 끝나기 때문입니다. 다시 말해서, 심사관 A가 1분 늦게 비더라도 심사관 A에게 가면 2분 더 빨리 심사를 끝낼 수 있습니다.

우리는 어떤 심사관이 가장 먼저 비는지 보다는 어떤 심사관이 가장 먼저 심사를 끝낼 수 있는지가 더 중요하다는 것을 알 수 있습니다.

따라서 이 문제를 풀려면 시간이 흘러감에 따라 각 심사관이 심사를 끝낼 수 있는 시간을 추척해야 합니다. 그리고 가장 심사를 먼저 끝낼 수 있는 심사관에게 다음 사람을 계속해서 반복적으로 보내면 됩니다. 자연스럽게 선택받은 심사관의 심사를 끝낼 수 있는 시간은 늘어나게 되겠지요.

그럼 이 알고리즘을 파이썬으로 구현해볼까요?

def solution(n, times):
    ends = [0] * len(times) # 각 심사관의 심사가 끝나는 시간
    min_end = 0
    for _ in range(n):
        min_idx = 0
        for idx in range(1, len(ends)):
            if ends[idx] + times[idx] < ends[min_idx] + times[min_idx]:
                min_idx = idx
        ends[min_idx] += times[min_idx]
        min_end = ends[min_idx]
    return min_end

n을 사람의 수, t를 심사관의 수라고 했을 때, 이 풀이의 시간 복잡도는 이중 루프로 인해서 O(n * t)가 됩니다. 각 심사관이 심사를 끝낼 수 있는 시간을 저장하는 배열의 크기는 t와 비례하기 때문에 공간 복잡도는 O(t)가 되겠습니다.

풀이 2

위 풀이는 한 사람 한 사람을 일일이 심사관에게 보내면서 조금씩 심사가 끝나는 시간을 더해가고 있는데요. 만약 각 사람이 어떤 심사관에 가야 하는지까지는 구해야 되는 문제였다면, 이러한 접근 방식도 나쁘지 않았을 겁니다.

그런데 이 문제에서는 단순히 모든 사람이 심사를 받는데 걸리는 최소 시간을 구하라고 하고 있기 때문에 뭔가 비효율적으로 문제를 풀었다는 느낌이 드는 것 같습니다.

만약에 반대로 사람의 수 대신에 심사가 끝나는 시간이 우리에게 주어진다면 그 시간동안 최대 몇 명의 사람을 심사할 수 있을지 생각해보면 어떨까요? 예를 들어, 주어진 예제에서 15분이 주어진다면 최대 3명을 심사할 수 있다는 것을 알 수 있는데요. 심사관 A는 15분 // 7분 = 2명 심사 가능하고, 심사관 B는 15 // 10 = 1명 심사 가능하므로 총 2 + 1 = 3명을 심사할 수 있기 때문입니다. 즉, 주어진 시간을 각 심사관이 검사하는데 걸리는 시간으로 나눈 몫을 소수부를 버리고 모두 더하면 그 시간동안 최대 몇 명의 사람을 심사할 수 있을지를 알아낼 수 있습니다.

그리고 제한 사항에 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하라고 되어 있는데요. 사실 심사가 아무리 오래 걸려도 모든 사람이 한 명의 심사관에게 가서 심사를 받을 때보다는 오래 걸리지 않을 것입니다. 특히, 심사를 받는데 걸리는 최소의 시간을 찾아야하는 경우라면, 모든 사람이 가장 심사 속도가 빠른 심사관에게 찾아갔을 때 걸리는 시간보다는 무조건 적을 것입니다.

이렇게 탐색 범위의 상한과 하한을 알면 이분 탐색(Binary Search)으로 원하는 값을 찾을 수 있습니다. 예를 들어, 주어진 예제에서, 하한은 1분이고 상한은 가장 빠른 심사 시간인 7에 사람의 수 6을 곱해서 42가 됩니다. 즉, 우리가 찾고자 하는 값을 1과 42 사이에서 이분 탐색을 할 수 있습니다.

1과 42의 중간값은 1 + 42 // 2 = 21입니다. 21분 만에 몇 사람이 심사 받을 수 있는지 어떻게 알 수 있을까요? 각 심사관이 21분 동안 몇 사람을 심사할 수 있는지를 계산해서 모두 합치면 됩니다.

심사관 A는 21 // 7 = 3명 심사 가능하고, 심사관 B는 21 // 10 = 2명 심사 가능하므로 총 3 + 2 = 5명을 심사할 수 있습니다. 21분 만에는 주어진 7명을 모두 심사할 수 없으므로, 찾으려는 값이 중간 값인 21분 보다는 무조건 크다는 것을 알 수 있습니다.

start=1, end=42, mid=21, count=5 < 6

그럼 시작값을 중간 값에서 1을 더한 21 + 1 = 22로 갱신하고, 다시 탐색을 하겠습니다. 이번에는 중간값이 22 + 42 // 2 = 32입니다. 주어진 32분 만에 심사관 A는 32 // 7 = 4명 심사 가능하고, 심사관 B는 32 // 10 = 3명 심사 가능하여 총 4 + 3 = 7명을 심사할 수 있습니다. 그러므로 우리가 찾으려는 최소값이 중간 값인 32분 보다 작을 가능성이 있습니다.

start=22, end=42, mid=32, count=7 > 6

그럼 끝값을 중간 값에서 1을 뺀 32 - 1 = 31로 갱신하고, 다시 중간값을 구해보면 22 + 31 // 2 = 26이 됩니다. 주어진 26분 만에 심사관 A는 26 // 7 = 3명 심사 가능하고, 심사관 B는 26 // 10 = 2명 심사 가능하여 총 3 + 2 = 5명을 심사할 수 있습니다. 그러면 여기서 우리는 찾으려는 최소값이 중간 값인 26분 보다는 무조건 크다는 것을 알 수 있습니다.

start=22, end=31, mid=26, count=5 < 6

그럼 시작값을 중간 값에서 1을 더한 26 + 1 = 27로 갱신하고, 다시 중간값을 구해보면 27 + 31 // 2 = 29이 됩니다. 주어진 29분 만에 심사관 A는 29 // 7 = 4명 심사 가능하고, 심사관 B는 29 // 10 = 2명 심사 가능하여 총 4 + 2 = 6명을 심사할 수 있습니다. 그러므로 우리가 찾으려는 최소값이 중간 값인 29분 보다 작을 가능성이 있습니다.

start=27, end=31, mid=29, count=6 == 6

그럼 끝값을 중간 값에서 1을 뺀 29 - 1 = 28로 갱신하고, 다시 중간값을 구해보면 27 + 28 // 2 = 27이 됩니다. 주어진 27분 만에 심사관 A는 27 // 7 = 3명 심사 가능하고, 심사관 B는 27 // 10 = 2명 심사 가능하여 총 3 + 2 = 5명을 심사할 수 있습니다. 그러면 여기서 우리는 찾으려는 최소값이 중간 값인 28분 보다는 무조건 크다는 것을 알 수 있습니다.

start=27, end=28, mid=27, count=5 < 6

그럼 시작값을 중간 값에서 1을 더한 27 + 1 = 28로 갱신하고, 다시 중간값을 구해보면 28 + 28 // 2 = 28이 됩니다. 주어진 28분 만에 심사관 A는 28 // 7 = 4명 심사 가능하고, 심사관 B는 28 // 10 = 2명 심사 가능하여 총 4 + 2 = 6명을 심사할 수 있습니다. 그러므로 우리가 찾으려는 최소값이 중간 값인 28분 보다 작을 가능성이 있습니다.

start=28, end=28, mid=28, count=6 == 6

끝값을 중간 값에서 1을 뺀 28 - 1 = 27로 갱신하게 되면, 시작값인 28보다 작아지게 되어 탐색을 중단할 수 있습니다. 이런 식으로 계속해서 탐색 범위를 좁혀나가다가 보면 최종적으로 시작값에 모든 사람을 심사하는데 걸리는 최소 시간이 들어있게 됩니다.

지금까지 다소 장황하게 설명드린 알고리즘을 파이썬으로 구현해보겠습니다.

def solution(n, times):
    start, end = 1, min(times) * n

    while start <= end:
        mid = (start + end) // 2

        cnt = 0
        for time in times:
            cnt += mid // time

        if cnt < n: # 중간값보다 무조건 더 많은 시간 걸림
            start = mid + 1
        else: # 중간 값보다 적은 시간이 걸릴 여지가 있음
            end = mid - 1

    return start

이 이분 탐색을 활용한 풀이의 시간 복잡도는 O(log n * t)로 향상됩니다. 고정된 개수의 변수외에 추가 메모리도 사용하지 않으므로 공간 복잡도도 O(1)로 개선됩니다.