[이분탐색] 프로그래머스 입국심사 - 파이썬 Python

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

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

생각하기

처음에는 모든 경우를 살펴보자는 생각이었지만 n의 개수와 시간이 너무 커서 불가했다

이분 탐색으로 풀기 위해서 기준을 정해야 하지만 어떤 기준을 정해야할지 생각하는데에 오래 걸렸다

 

이분 탐색의 기준을 심사 시간이라고 가정 = 각 심사관이 사람을 처리할 수 있는 시간

• right (max)는 가장 오랜 시간이 걸리는 심사관이 모든 사람(n)을 처리했을 때, n * max(times)
• left (min)은 시간 1

시간복잡도

시간이 mid로 주어졌을 때, 각 심사관이 mid 시간동안 몇명의 사람을 처리했는지 모든 처리 사람 수를 더하고 

그게 n 이상이 되는지 안되는지에 따라 범위를 좁혀가면 된다

 

1부터 max 시간까지의 모든 시간을 이분 탐색을 통해 logN 시간으로 찾을 수 있다

 

접근방식

처음 문제를 볼 때는 심사관들을 linear하게 생각해서 심사관들을 시간 선상에 배치해서 생각했는데

심사관들이 사람을 처리하는 것을 병렬적으로 생각하는 것이 접근에 옳다

 

mid 즉, 시간을 심사관이 심사에 걸리는 시간으로 나누면 (mid // t)

결국 촘촘히 모든 시간을 심사관들이 사용했을 때 몇명을 심사했는지 알 수 있다

 

 

구현하기

mid, left, right을 두어서 이분 탐색을 진행

• mid 시간에서 처리 가능한 수의 합이 n보다 크거나 같은 경우 범위를 왼쪽으로 줄인다
• mid 시간에서 처리 가능한 수의 합이 작은 경우 mid+1을 left에 넣어서 범위를 오른쪽으로 줄인다

 

left >= right 일 때, while문을 빠져나간 후 

answer로는 right를 출력

• left와 right가 같은 경우 right 혹은 아무거나 출력하면 된다
• left가 right보다 큰 경우는 결국 mid 시간에서 처리가능한 수의 합이 작아서 범위를 오른쪽으로 좁힌 경우인데 이 경우 right는 항상 n보다 크거나 같은 경우를 뜻하므로 이때의 최소는 right의 값이 된다

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