문제 개념 정리

1. 이분탐색 = 이진탐색
2. 왼쪽부터 순서대로 탐색하지 않고, 문제의 크기를 절반으로 줄이면서 탐색
   2-1. 리스트의 mid(중앙)항목을 조사하고, 탐색키가 해당항목보다 크다면 찾는 항목은 해당 항목 왼쪽에 위치해있고, 나머지 오른쪽 항목은 검사할 필요가 없다. -> 시간 단축
   2-2. 이런식으로 계속 반복하여 left = right가 될 때의 mid항목을 반환

문제 요약

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

문제 접근

이진 탐색을 할 때는

• 이진탐색의 범위는 어디까지 잡아야할지
• 탐색키는 무엇으로 할지 를 정해야한다.

1. left = 1, right = max(times) * n 으로 정한다.
   1-1. max(times) * n : 가장 비효율적으로 모든 사람을 심사하는 데 걸리는 시간
2. mid(분) 계산한다.
3. 탐색키는 mid분동안 심사 가능한 사람 수(변수명: people)로 잡고, times(심사대)를 돌면서 mid분동안 심사 가능한 사람 수를 구한다.
4. 심사가능한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우, mid분은 모두를 심사하기 충분한 시간에 해당되는 것이므로 "걸리는 시간의 최소값"은 mid의 왼쪽범위 어딘가에 있다. 즉 right는 mid - 1로 갱신
5. 심사가능한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우, mid분은 모두를 심사하기 부족한 시간에 해당되는 것이므로 "걸리는 시간의 최소값"은 mid의 오른쪽 범위 어딘가에 있다. 즉 left를 mid + 1로 갱신
   ※ 이해가 안된다면 이 블로그의 그림 설명을 참고하세요
6. left <= right인 경우에 2~5과정을 반복한다. 그리고 left>right일 때 break하고 answer을 반환

코드

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n 
    while left <= right:
        mid = (left + right) // 2
        people = 0   # mid분동안 심사 가능한 사람 수
        for time in times:
            people = people + (mid // time)  # 예: mid=33일 떄, 33//7 + 33//10 = 7
        if people >= n:     # 심사가능한 사람의 수(people)가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
            answer = mid    # 최소 걸리는 시간을 mid분으로 갱신
            right = mid - 1
        elif people < n:  # 심사가능한 사람의 수(people)가 심사 받아야할 사람의 수(n)보다 적은 경우
            left = mid + 1
            
    return answer