프로그래머스 Level3 "입국심사"

문제

프로그래머스 '입국심사'

풀이

분류가 이분탐색으로 되었있었는데 어떠한 방식으로 이분탐색을 이용해야되는지 오래 고민했던 문제.

나는 심사관들에게 시간을 주고 이 시간동안 심사관들이 몇명의 사람들을 심사하는지 체크하고,
각 심사관들이 심사한 사람수의 합이 n명인 최소값을 찾는 방식을 택했다.

• 1부터 n * max(times)(최악의 경우인 가장 시간이 오래걸리는 심사관에게 모든 사람들이 심사받는 경우)까지의 범위를 가지고 이분 탐색을 시작하여야 한다.
• mid값이 심사관들에게 주어진 시간이라고 할때, 시간내에 심사관들이 심사할 수 있는 사람들의 수가 n보다 크냐 작냐에 따라 범위를 조정한다.

Python 코드

# n명을 심사하는 최소의 시간을 찾아야 함
# 최적의 시간을 찾을 때 까지 이분 탐색 반복
def solution(n, times):
  # 1과 최악의 시간(모두가 가장 시간이 오래걸리는 심사관에게 심사를 받을경우)을 좌, 우로 설정
  start, end = 1, n * max(times)

  # 이분 탐색 시작
  while start <= end:
    # mid = 심사관에게 주어진 시간
    mid = (start+end) // 2

    # mid값 안에서 각 심사관이 심사할 수 있는 사람의 수 확인
    count = 0
    for x in times:
      count += mid // x
    
    # 현 mid값에서 심사관이 n보다 많은 사람들을 심사할 수 있을 경우
    # end값을 줄여 범위를 하향 조정한다
    if count >= n:
      end = mid -1
      answer = mid
    # 현 mid값에서 심사관이 n보다 적은 사람들을 심사할 수 있을 경우
    # start값을 높여 범위를 상향 조정한다
    else:
      start = mid + 1
  
  return answer