[Programmers] 입국심사

출처: 프로그래머스 코딩 테스트 연습
https://programmers.co.kr/learn/courses/30/lessons/43238

이분탐색 (Binary Search Algorithm)

• 정렬이 된 배열에서 탐색범위를 절반으로 줄여 탐색하는 알고리즘
• 왼쪽 끝 인덱스를 start, 오른쪽 끝 인덱스를 end라고 지정하고 중간 인덱스인 mid를 이용
• mid와 target을 비교해서 target<mid이면 왼쪽 배열에서, target>mid이면 오른쪽 배열에서 target을 찾을 때까지 탐색 과정 반복
• 선형 탐색보다 빠르게 탐색 가능, 시간복잡도는 O(logn)

📝 풀이 (python3)

def solution(n, times):
    times.sort() 
    start = 0
    end = n * times[0] # 최대로 걸리는 시간은 심사받는 최소의 시간을 n번 수행하는 경우
    while start <= end:
        cnt = 0
        mid = (start + end) // 2 # mid는 정수여야 하므로 몫으로 지정해줌
        for t in times: # 총 걸리는 시간이 mid일 때 심사받는 사람의 수 계산
            cnt += (mid // t) # mid를 t로 나눈 몫은 각 심사대에서 심사받는 사람의 수
            if cnt > n : # cnt가 n이 되는 mid값을 구하고 싶으므로 효율성을 위해 cnt가 n을 넘으면 break
                break
        if cnt < n:
            start = mid
        else:
            end = mid
        if start + 1 == end:
            if cnt < n :
                mid += 1
            break
    return mid