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

문제

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

프로그래머스

---

접근

이분탐색 풀이

범위 : 심사에 걸리는 최소 시간 ~ 심사에 걸리는 최대 시간 * 사람 수

mid : 임의의 시간, mid // time 은 임의의 시간동안 해당 심사대가 심사할 수 있는 사람 수를 계산한 것

기준 :

1. mid 동안 심사한 사람 수(people)이 n보다 크거나 같으면 시간이 충분한 것이므로, right 조정
2. mid 동안 심사한 사람 수(people)이 n보다 작으면 시간이 부족한 것이므로, left 조정

left = right 가 되는 순간 mid가 최적의 시간이다.

---

코드

# 임의의 시간을 구하고, 그 시간동안 몇명이 심사를 받을 수 있는 지 확인하며 이분탐색한다.

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times) * n
    
    while left <= right:
        mid = (left + right) // 2
        people = 0
        for time in times:
            people += mid // time
            
            if people >= n:
                break
        if people >= n:
            answer = mid
            right = mid - 1
            
        else:
            left = mid + 1
        
    return answer