프로그래머스 입국심사 파이썬 | 이분탐색

코테볼때 binary search로 해결 가능한 문제를 sorting 을 해서 망했다:(
문제에 분명 O(logN)으로 풀라고 되어있었지만 바이너리 서치로 풀어야한다는 감조차 안왔어서 이 기회에 문제를 풀면서 익혀봐야겠다

문제링크

중요 포인트

• target
• min
• max
• mid

위의 값들을 먼저 세팅해두고 접근해보자
먼저 시간범위(min, max)를 생각해보면 최솟값은 1, 최대값은 (가장 오래 걸리는 시간 X n명) 이다

이 문제의 테스트케이스에서 보면 최댓값은 10x6 = 60분 이고 mid는 (60+1)//2 = 30분이 된다

30분동안 심사가능한 사람의 수는
7분 걸리는 심사관 -> 4명가능
10분 걸리는 심사관 -> 3명가능
이렇게 토탈 7명의 심사가 가능하다

즉, 여기서 주어진 사람의 수는 6명이므로 30분보다 덜 걸린다는 소리다.
1. 심사 가능한 사람이 주어진 사람보다 많다면?

• 최댓값을 중간값으로 해서 범위를 줄여준다 (max = 30)

2. 심사 가능한사람보다 주어진 사람이 많다면?

• 최솟값을 중간값으로 해서 범위를 줄여준다 (min = 30)

def solution(n, times):
    start, end = (times[0], max(times)*n)
    
    while start < end:
        mid = (start + end) // 2
        total = 0 # 총 심사 가능한 사람
        for time in times:
            total += mid // time
        if total >= n:
            end = mid 
        else:
            start = mid + 1
            
    return start