• 이분탐색 알고리즘 문제 : 프로그래머스 LEVEL 3(입국심사))

    image

    • 사용 언어 : python

    • 해결 날짜 : 2021-05-04

    • 해결 방법 :

      • 이진 탐색을 위한 시작점과 끝점을 설정한다. 여기서 끝점은 최대 시간의 계산대에서 K명이 전부 계산한 경우이다.

      • 이진 탐색을 수행하며 mid시간 안에 있는 계산대 일 때만 계산한 사람의 수를 추가해준다.

      • 계산한 사람의 수가 계산이 끝났을 때 계산한 사람의 수가 모자란 경우 더 많은 시간을 부여하고(오른쪽 부분 탐색), 충분한 경우 더 적은 시간을 부여한다(왼쪽 부분 탐색).

    • 코드

    def solution(n, times):
# 이진 탐색을 위한 시작점과 끝점
# 끝점은 최대 시간의 심사관한테서 n명이 전부 심사한 경우
start = 0
end = max(times)*n

# 이진 탐색 수행
result = 0
while start <= end:
    total = 0
    count = 0
    mid = (start + end) // 2
    for x in times:
        # mid 시간안에 있는 심사대에서만 심사 가능
        if x <= mid:
            # 심사받은 사람의 수 계산
            count += mid // x
    # 심사받은 사람의 수가 모자란 경우 더 많은 시간을 부여(오른쪽 부분 탐색)
    if count < n:
        start = mid + 1
    # 심사받은 사람의 수가 충분한 경우 더 적은 시간을 부여(왼쪽 부분 탐색)
    else:
        result = mid  # 최소 시간을 찾는 것 이므로 저장해놓음
        end = mid - 1

return result