프로그래머스 입국심사 (Python)

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

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

서론

이제 프로그래머스 3단계에 진입했다. 그 첫문제가 입국심사이다.
문제 분류에 이분탐색이라고 적혀있어서 도전해봤다.

풀이

하지만 설계하는 과정이 쉽지 않았다. 과연 무엇을 기준으로 이분탐색을 해야 정확한 시간을 계산할 수 있을까?

이 예제를 봤을때 return 된 시간을 각각의 시간으로 나눈 몫이 n이라는 것을 포착했다.

그러면 가장 긴시간 (제일 오래 걸리는 사람이 모두 심사하는경우)를 두고 이분탐색을 통해서 정답을 맞추면 되겠다.

그리고 그 방법은 중간값 // 심사시간 들을 더하고 n 이랑 비교하면 되겠다.
이 말은 중간값(예상시간)에 걸리는 사람들을 비교해보고 더 많은 사람을 검사할 수 있는 시간이면 시간을 줄이고, 더 적은 사람밖에 비교를 못하면 시간을 늘려주면서 딱 맞는 시간을 찾아주면 되겠다!

def solution(n, times):
    answer = 0
    start = 1
    end = n * max(times)
    while start < end:
        mid = (start+end) // 2
        total = 0
        for time in times:
            total += mid//time
        if n <= total:
            answer = mid
            end = mid
        else:
            start = mid + 1
    return answer

후기

무엇을 구하려는지 체크하고 풀이를 해나가는 습관을 기르자