[Binary Search] 입국심사

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

프로그래머스

 

def search(n, times, mid):
    cnt = 0

    for t in times:
        cnt += mid // t
    return True if cnt >= n else False

def solution(n, times):
    start = 0
    end = min(times) * n
    mid = start
    
    while mid + 1 != end:
        mid = (start + end) // 2
        if search(n, times, mid):
            end = mid
        else:
            start = mid
        
    return end


n = 6
times = [7, 10]

result = solution(n, times)
print(result)

해당 문제는 이진 탐색으로 해결할 수 있습니다.

정렬된 리스트만 이진 탐색 대상이 될 수 있으며, 이진 탐색은 시작점과 끝점을 설정하고 적절한 중간점을 잡아야 합니다.

 

주어진 예시에서 첫 번째 심사관의 심사 시간은 7분이므로, 6명의 입국심사 시간은 최대 42분입니다.

따라서 시작점을 0, 끝점을 42로 설정합니다.

중간점은 시작점과 끝점을 더하고 2로 나누어 계산합니다.

 

search() 함수는 이진 탐색의 범위를 어떻게 줄일지(시작점을 높일지, 끝점을 줄일지) 결정합니다.

중간점을 각 심사관의 심사 시간으로 나누어 몇 명까지 심사를 할 수 있을지 계산합니다.

만일 심사를 할 수 있는 인원 수가 6명 이상일경우 끝점을 중간점으로 설정합니다.

이와 반대로 심사를 할 수 있는 인원 수가 6명보다 적을 경우시작점을 중간점으로 설정합니다.

 

solution()함수에서 각 변수 상태 변화는 아래와 같습니다.

스텝	시작점	중간점	끝점	심사관1의 심사 인원	심사관2의 심사 인원	심사 인원 합
1	0	21	42	3	2	5
2	21	31	42	4	3	7
3	21	26	31	3	2	5
4	26	28	31	4	2	6
5	26	27	28	3	2	5

스텝4에서 6명의 입국심사를 진행할 수 있습니다. 따라서 더 적은 시간에 심사를 할 수 있는지 파악하기 위해 끝점을 중간점으로 설정합니다. (31→28)

스텝5에서 중간점과 끝점의 차이가 1이기 때문에 탐색이 종료되었으므로 최소 심사 시간은 끝점에 저장된 28분입니다.