[프로그래머스] 입국심사

---

문제 링크

---

def solution(n, times):
    answer = 0
    times.sort()
    left = 1 # 최소 시간
    right = max(times) * n # 최대 시간
    # 대상 : 검색 시간의 범위
    while left <= right: 
        mid = (right + left) // 2 
        remain_cnt = n  # 남아있는 사람 수
        for time in times: 
            remain_cnt -= mid // time
            if remain_cnt <= 0: 
                answer = mid 
                right = mid - 1 
                break 
        if remain_cnt > 0: 
            left = mid + 1 
    return answer

• 이진 탐색
  이진 탐색을 이용해 시간 복잡도를 줄인다.

• 최소 시간
  제한 사항에서
  입국심사를 기다리는 사람은 1명 이상, 한 명을 심사하는데 걸리는 시간이 1분 이상이기 때문에 최소 시간은 1분이라고 할 수 있다.

• 최대 시간
  가장 느린 심사위원의 시간이 모든 심사위원에게 적용되는 경우이다.

    right = max(times) * n

• 풀이 과정

1. 걸리는 시간의 최소와 최대를 이진탐색의 left, right로 설정한다.
2. 이진 탐색 시간을 사용하여 각 심사위원들이 몇명을 처리할 수 있는지 계산한다.
   • remain_cnt가 0 이하이면 모든 사람을 다 처리하였으므로
     정답을 저장해놓고(answer = mid),
     더 짧은 시간에 처리할 수 있는지 확인하기 위해 right = mid - 1로 설정한다.
   • times 에 대한 for문을 반복해도 remain_cnt가 0보다 크다면
     주어진 시간(mid)안에 모든 사람을 처리하지 못한 것이므로,
     left = mid + 1로 설정한다.
3. 걸리는 시간을 계속하여 이분탐색하며 반복문을 돌아주며 최소 시간을 구한다.

---

이진 탐색이라는 힌트가 있어도 못 풀었던 문제.
이진 탐색의 대상을 찾는 게 정말 힘든 듯하다..