[프로그래머스/Python] 입국심사 - Level3

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

코딩테스트 연습 - 입국심사

이 문제는 이분탐색 문제였다. 어느 부분을 이분 탐색하는지 감이 잡히지 않아서 다른 사람들이 푼 방법을 보고 코드를 짰다. 

def solution(n, times):
    answer = 0
    left = 1 
    right = max(times) * n
    
    # 이분탐색 수행
    while left < right:
        mid = (left + right) // 2
        count = 0
        
        for t in times:
            count += mid // t # 심사할 수 있는 인원
        
        if count >= n: # n명을 심사할 수 있다면
            answer = mid
            right = mid
        else: # n명을 심사할 수 없다면
            left = mid + 1
            
    return answer

1. left = 1, right = max(times) * n 으로 초기화한다. right 는 가장 오래 걸리는 최악의 심사 기간이다.

2. 이분 탐색을 수행한다.

    2-1. mid 를 구한 후 심사할 수 있는 인원(count) 를 계산한다.

    2-2. n명을 심사할 수 있다면 현재 탐색한 구간보다 아래쪽에서 탐색한다

    2-3. n명을 심사할 수 없다면 현재 탐색한 구간보다 위쪽에서 탐색한다

 

처음에는 while left <= right 로 했더니 시간초과가 났다. while left < right 으로 수정했더니 해결되었다. 이 작은 차이에 시간초과인지 아닌지가 갈리는 것이 신기했고 조심해야겠다고 생각했다.