[이분탐색] 프로그래머스. 입국심사

문제

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3

문제요약

n 명의 사람들이 대기하고 있다, list에는 창구별 대기시간이 주어진다.
사람들이 볼일을 다 보는 시간은 언제일까요?

풀이

어제 푼 도토리랑, k번째 숫자를 생각하며 하나씩 추가하는 관점이 아니고
그 시간이 됐을 때 몇 명이 빠졌을까를 생각해보니 답을 추론할 수 있었다.
6명이 대기하고 있다면, 6명이 다 빠졌을 시간을 구하는 것이다.
n = 6, w = [7,10]
예를 들어, 7분이 됐을 때는 1명이 볼 일을 다 본 상태일 것이고
10분이 됐을 때는 2명이 볼 일을 다 봤을 것이다. 즉 ( time 을 기준으로 창구별 대기시간의 몫) 의 합이 이미 볼 일 다 본 사람들의 수가 된다.
time의 탐색 범위는 0분터 최대 10의 18제곱이다. 창구대기 시간이 10의 9제곱 일 수 있는데, 사람이 10의 9제곱만큼 올 수 있어서다. 즉, 어어엄청 오래 걸리는 창구 하나만 가동되는데 사람이 제애ㅔㅔㅔㅔ일 많이 왔을 때 걸리는 시간이 time의 최대값이고, 탐색범위의 마지막 숫자(high)가 된다.

import sys
def search(time,w):
    add = 0
    for t in w:
        add += (time//t)
    return add

def solution(n, w):
    answer = 0
    time = 0
    low = 0
    high = 10**(9+9)
    while low <= high:
        time = (low+high) //2
        print(time, answer)
        if search(time,w) < n:  # 가장 먼저 창구별로 사람 넣고 시작
            low = time+1
        else:
            high = time-1
            answer = time

    return answer