[프로그래머스/Python] 이분탐색 - 입국심사

접근 방법

• 임의의 시간 동안 몇 명이 심사 받을 수 있는지 확인하고 이 값을 최소로 만들기
• 시간의 최소, 최대 범위를 구하고 중간 값이 n명을 심사 할 수 있는 시간인지 확인하며 이분 탐색을 진행
  중간 값 시간 동안 ,
• n명보다 많이 심사 가능 -> 중간값 기준 왼쪽 범위 탐색
• n명보다 적게 심사 가능 -> 중간값 기준 오른쪽 범위 탐색
• 임의의 시간동안 몇 명을 심사 할 수 있는지 확인하는 방법

풀이

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times) * n
    while left <= right:
        mid = (left + right) // 2
        check = 0
        for time in times:
        	# check는 모든 심사관들이 mid분 동안 심사한 사람의 수
            check += mid // time
            # mid분 동안 심사한 사람의 수가 n명 이상의 심사를 할 수 있다면 break
            if check >= n:
                break
        # 심사한 사람의 수가 심사 받아야할 사람의 수보다 많거나 같은 경우
        if check >= n:
            answer = mid
            right = mid -1
        # 심사한 사람의 수가 심사 받아야할 사람의 수보다 적은 경우
        elif check < n:
            left = mid + 1
    return answer

• right = 가장 비효율적으로 심사했을 때 걸리는 시간 = 가장 긴 심사시간이 소요되는 심사관에게 n명 모두 심사받는 경우
• left <= right 경우
  • mid = (7 + 60) // 2 = 33
  • for time in times:
    • check = 0 + 33 // 7 = 4, 4는 6보다 크거나 같나? No
    • check = 4 + 33 // 10 = 7, 7은 6보다 크거나 같나? Yes -> break
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
    • answer = mid = 33
    • right = 32

    ---

  • mid = (7 + 32) // 2 = 19
  • for time in times:
    • check = 0 + 19 // 7 = 2, 2는 6보다 크거나 같나? No
    • check = 2 + 19 // 10 = 3, 3은 6보다 크거나 같나? No
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
    • left = mid + 1 = 20

    ---

  • mid = (20 + 32) // 2 = 26
  • for time in times:
    • check = 0 + 26 // 7 = 3, 3는 6보다 크거나 같나? No
    • check = 3 + 26 // 10 = 5, 5은 6보다 크거나 같나? No
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
    • left = mid + 1 = 27

    ---

  • mid = (27 + 32) // 2 = 29
  • for time in times:
    • check = 0 + 29 // 7 = 4, 4는 6보다 크거나 같나? No
    • check = 4 + 29 // 10 = 6, 6은 6보다 크거나 같나? Yes
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
    • answer = mid = 29
    • right = 28

    ---

  • mid = (27 + 28) // 2 = 27
  • for time in times:
    • check = 0 + 27 // 7 = 3, 3은 6보다 크거나 같나? No
    • check = 3 + 27 // 10 = 5, 5은 6보다 크거나 같나? No
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
    • left = mid + 1 = 28

    ---

  • mid = (28 + 28) // 2 = 28
  • for time in times:
    • check = 0 + 28 // 7 = 4, 4는 6보다 크거나 같나? No
    • check = 4 + 28 // 10 = 6, 6은 6보다 크거나 같나? Yes
  • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
    • answer = mid = 28
    • right = 27

    ---

• left > right로 반복문 탈출!