파이썬(Python) 알고리즘 문제풀이 입국 심사[프로그래머스 / 이분탐색]

출처) 프로그래머스 Facebook

문제 설명

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

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

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

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

 

 

제한사항

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.

 

 

입출력 예시

n	times	return
6	[7, 10]	28

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

 

풀이 코드

모든 사람들이 입국 심사를 받는 최소 시간을 찾아내는 문제이고, n 이 최대 1억까지 주어지는 문제이기 때문에 완전탐색은 무조건 실패하는 문제이다. 따라서 이분 탐색을 의심해볼 수 있고, 어떤 기준을 잡아내야하는지 고민했다. 최소 시간을 찾아내야하는 문제니까 임의의 시간을 기준으로 잡고, 해당 시간에 몇 명이 입국 심사를 받을 수 있는지 계산한다. 만약 주어진 n 명보다 더 많은 사람들 심사할 수 있다면, 임의의 시간이 넉넉하다는 뜻이므로 (최소 시간이 아니라는 뜻) 임의의 시간을 줄여주고, 주어진 n 명보다 적은 사람을 심사할 수 있다면, 임의의 시간이 부족하다는 뜻이므로 임의의 시간을 늘려주는 방식으로 풀이했다. (파라메트릭 서치를 활용)

checked_people_count >= n 로직에 걸린 mid_time 이 무조건 최소 시간이라는 보장이 없기 때문에 min() 함수를 활용해 계속 최소 값을 찾아 갱신 해줘야한다.

def solution(n, times):
    # 최소 시간을 찾아내기 위해 answer 를 크게 잡아준다.
    answer = 1e15

    # times 리스트에서 어떤 것을 찾아내는게 아니기 때문에 굳이 times 리스트를 정렬할 필요는 없다.
    # 기준을 "시간" 으로 잡았기 때문에 최소한 걸리는 시간을 left 로 잡아준다.
    # 입국 심사에 걸리는 최대의 시간을 right 로 잡아준다.
    left = min(times)
    right = max(times) * n

    while left <= right:
        mid_time = (left + right) // 2
        checked_people_count = 0

        for time in times:
            # 정해진 임의의 시간에서 몇 명을 검사할 수 있는지 확인한다.
            checked_people_count += mid_time // time

        # 몇 명을 검사할 수 있는지 파악했다면, 주어진 n 명과 비교한다.
        # 현재 정해진 임의의 시간에서 검사할 수 있는 인원이 주어진 n 명보다 많거나 같다면 임의의 시간이 넉넉한 것이기 때문에
        # 임의의 시간인 mid_time 을 줄여줘야한다.
        # 또한, 검사할 수 있는 인원과 n 이 같은 경우 현재 임의의 시간이 최소 시간인지 판단한 뒤 계속 갱신해줘야 한다.
        if checked_people_count >= n:
            answer = min(answer, mid_time)
            right = mid_time - 1

        # 현재 정해진 임의의 시간에서 검사할 수 있는 인원이 주어진 n 명보다 적다면 임의의 시간이 부족한 것이기 때문에
        # 임의의 시간인 mid_time 을 늘여줘야한다.
        elif checked_people_count < n:
            left = mid_time + 1

    return answer