[프로그래머스/LV3/이분탐색] 입국검사

문제링크

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

프로그래머스

 

def solution(n, times):
    answer = 1e18
    # 모든 사람이 심사를 받는데 걸리는 시간의 최솟값
    # start = mid+1 , end = mid-1
    # max = max(time)*n
    # 30초에 모든 사람이 심사를 받을 수 있는가?
    # 7/14/21/28
    # 10/20/30
    # 모든 검색대 시간의 배수를 정렬하고, 거기서 인원수를 카운트한다
    # 30//7 = 4 + 30//10 = 3 -> 7명까지 가능
    ## 15//7 = 2 + 15//10 = 1 -> 3명까지 가능
    ## 22//7 = 3 + 22//10 = 2 -> 5명까지 가능
    ## 26//7 == 3 + 26//10 = 2 -> 5명까지 가능
    ## 28//7 == 4 + 28//10 = 2 -> 6명까지 가능
    
    start = 1
    end = max(times)*n
 
    while start <= end:
        mid = (start+end)//2
        
        arr = list(map(lambda x : mid//x,times))
        
        hap = sum(arr)
        
   
        
        if hap >= n:
            answer = min(answer,mid)
            end = mid-1
        else:
            start = mid+1
    
 
    return answer

 

풀이

1. 처음부터 이분탐색이라는 조건하에 입국심사를 할 수 있는 최소값을 구하기 위해서는 심사를 하는데 걸리는 최대시간을 알아야한다. 이는 검색대에서 제일 오래 걸리는 심사관한테만 모든 입국자들이 검사를 받는 경우이다. 이에 max(times)*n으로 최대시간을 구할 수 있으며 end와 answer(최소시간을 구해야하기에 최댓값을 초기로 설정, 최대시간이면 0으로 설정)을 해당값으로 설정한다. 

 

2. 이제 주어진 mid 시간대에 최대 몇명이 통과할 수 있는지를 구해야하는데 이는 mid를 각 심사관들이 걸리는 시간으로 나눈 몫을 구하면 된다. 구체적으로 위의 예제인 [7,10]의 심사관과 시간이 있다면 30초의 시간대엔 7의 심사관은 4번 , 10의 심사관은 3명을 검사할 수 있기에 최대 7명까지 가능하다. 즉, 6명을 만족하기에 30초 보다 적은 시간대로 가능한지 확인해야한다.

 

3. 30초에서 절반인 15초에서는 몇명이 되는지 확인해보면 15//7, 15//10으로 최대 3명이 검사가능하다. 이는 6명을 만족하지 않기에 15초보다 더 큰 시간대로 확인한다. 이를 반복하다보면 최소 28초의 시간대에서 6명이 가능하다는 걸 알 수 있다.

 

4. 주어진 조건을 찾는 것은 빨리했지만, 만족하는 경우 어디에서 answer을 업데이트할지 찾는 것이 어려웠다. 이는 반복해서 문제를 풀다보면 보일 것이다. 그리고 배열에서 주어진 값이 1억이나 2억처럼 말도 안되는 숫자를 준다면 이분탐색을 고려해보는 것이 좋다.