[프로그래머스] Lv.3 입국심사 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43238
• 최악의 경우 : 1000000000, [1000000000]처럼 10억 명이 10억 분 걸리는 심사관 1명한테 심사 받을 경우 (100경 분)
  • 심사관이 1명일 때는 사람 수 * 심사 시간을 하면 바로 구할 수 있기 때문에 숫자 크기를 보는 게 아니라면 최악은 아닌 상황
• 두 번째 최악의 경우 : 1000000000, [1000000000, 1000000000] 10억 명이 10억 분 걸리는 심사관 2명한테 심사 (50경)
  • 심사관이 2명 이상일 경우는 바로 계산이 불가능하기 때문에 최댓값인 50경을 last 값으로 줬다.
  • 마지막 값을 정하는 더 좋은 방법이 있겠지만 최악을 생각함
• mid를 심사관들이 심사하는데 걸리는 시간으로 나눈 몫을 전부 더하면 mid 시간 안에 몇 명을 심사할 수 있는지 알 수 있다. (sum)
• 손님 수 보다 sum이 많으면 시간이 여유가 있다는 것으로 시간을 줄인다.
• 손님 수 보다 sum이 적으면 시간이 부족하다는 것으로 시간을 늘린다.

def solution(n, times):

    first = 0

    last = 500000000000000000 # 두 번째 최악의 경우에 필요한 값

    sum = 0

    # 심사관이 1명일 때 사람수 * 심사시간을 바로 리턴

    if len(times) == 1:

        return times[0] * n

    while first <= last:

        mid = (first + last) // 2 # 기준 시간

        sum = 0

        for t in times:

            sum += mid // t # 기준 시간을 심사관들이 걸리는 시간으로 나눈 몫을 합한다.

        if n <= sum: # 시간 줄이기

            last = mid - 1

        if n > sum: # 시간 늘리기

            first = mid + 1

    return first