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

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

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

 

다른 사람 풀이

def solution(n, times):
    answer = 0
    
    left = 0
    right = max(times) * n # 최대 시간
    
    while left < right:
        total = 0 # 심사한 인원수
        mid = (left+right) // 2 # 현재 시간
        
        # mid만큼의 시간이 있을때 처리할 수 있는 인원 수 
        for time in times:
            total += mid//time
        
        # 검사 인원이 n보다 많으면 right 변경
        if total >= n:
            right = mid
        else: # 적으면 left 변경
            left = mid + 1
    answer = left
    return answer

 

풀이 설명

이분탐색 기법으로 풀라는데 뭘 어떻게 하라는건지 감이 안와서 결국 답안 참고...

 

이 문제에서 이분탐색 기준은 "시간"이다! 

left는 최소시간, right는 최대시간으로 설정한다. (times의 가장 max값*인원)

 

그리고 left와 right의 중간값인 mid를 설정한다.

해당 mid(시간)에서 처리할 수 있는 인원 수가 몇명인지 total에 저장한다.

 

이 total 인원 수가 n(처리해야 하는 인원수)보다 많으면, 시간이 넉넉~하단 뜻이므로 right를 조정한다.

반면 total 인원수가 n보다 적으면, 시간이 부족하다는 뜻이므로 left를 조정한다.

최종적으로 answer에는 left(가장 최소시간)을 입력한다!