[프로그래머스, 파이썬] 입국 심사 - 레벨 3 | 이분탐색(Binary Search)

📌 프로그래머스 - 입국 심사

<내 답안>

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

이분탐색을 사용하는 문제!
오랜만에 풀어봤더니 생각하느라 조금 시간이 걸렸다..

이분탐색은 간단하게 설명하면 중간부터 답을 찾아가는 기법이다.
left, right, mid 변수를 지정해 푸는 경우가 일반적이다.

left = 최솟값
right = 최대값
mid = 중간값 : (left+right)//2

이분탐색

답이 mid보다 작은 것으로 추정되면
최대값인 right를 mid - 1로 지정해주고 다시 탐색!
답이 mid보다 큰 것으로 추정되면
최솟값인 left를 mid + 1로 지정해주고 다시 탐색!
최솟값인 left가 right보다 커지면
탐색을 멈추고 현재 mid값을 답으로 반환!

보통 다음과 같은 form을 사용한다

def soltion():
	left = min()
	right = max()
	mid = (left+right)//2

	while left <= right:
    	
        ~~조건문~~
        
        if 조건:
        	answer = mid
            right = mid - 1
        elif 조건:
        	left = mid + 1
    
    return answer

위 같은 이분탐색 form을 외우면 단 번에 풀리는 문제!