[PG/python3] 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

---

알고리즘 분류

• 이진 탐색(이분 탐색)

문제

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
6	[10, 1]	6
6	[2, 5]	10

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다. 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다. 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다. 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다. 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

풀이

전체를 탐색하는데 걸리는 최대값과 최소값을 대략적으로 유추 할 수 있으며, 중간값을 구해 이 시간동안은 최대 몇 명의 사람이 검사 받는지 확인할 수 있다. 그리고 중간값을 토대로 최대와 최소중 누굴 변경할지 고려할 수 있다. 즉, 이진 탐색 문제다. 

탐색을 시행해보면 예제 입출력 1에 관해서 다음과 같이 동작한다.

min	mid	max
1	30	60
1	15	29
16	22	29
23	26	29
27	28	29
27	27	27

---

코드

def solution(n, times):
    # 최소 시간, 최대 시간 설정
    min_t = 1
    max_t = max(times) * n

    while min_t <= max_t: # 둘이 같거나 역전되면 종료
        # 중간 시간
        mid = (min_t + max_t) // 2
        # 중간 시간동안 검사 받을 수 있는 사람 수
        check = sum(mid // t for t in times)
        if check < n:# 목표치보다 적음 -> 최소를 증가시킴
            min_t = mid + 1
        else:# 최대를 줄임
            max_t = mid - 1
    return min_t