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

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

def solution(n, times):
    answer = 0
    left, right = 1, max(times) * n
 
    while left <= right:
        mid = (left + right) // 2
        
        # 주어진 시간(mid)동안 심사할 수 있는 인원수
        check = 0
        for time in times:
            # 걸릴 것으로 예상되는 시간에서 각 심사위원들이 심사할 수 있는 최대 인원수를 모두 더해본다
            check += mid // time

        # 최대 인원수보다 심사 가능한 인원이 많다면 예상되는 시간을 줄인다
        if check >= n:
            right = mid - 1
        # 최대 인원수보다 심사 가능한 인원이 작다면 예상되는 시간을 늘린다
        else:
            left = mid + 1
    
    # 마지막의 정답은 left값으로 설정
    answer = left
    return answer

# 최대로 걸리는 시간 -> 이분탐색의 range 1 ~ max time
# 이분탐색 -> left <= right 조건일 때 까지 반복 (while)
# 여기서 mid는 걸릴 것으로 예상되는 시간

 

문제 해결 Point

해당 문제의 핵심은 이분탐색을 활용하는데 target을 심사가 끝나는 최소시간으로 설정하는 것이다. 따라서, 탐색을 진행하면서 걸릴 것으로 예상 되는 시간을 mid로 정해두고 값을 늘리거나 더하면서 최소 시간을 찾아가는 방식이다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. 이분 탐색의 범위는 1분 ~ 가장 오래 걸리는 심사의 시간으로 정한다.
2. 이분 탐색의 알고리즘에 맞게 left <= right가 되는 동안 while 반복을 진행한다.
   1. 여기서 mid 값은 최소시간이 걸릴 것으로 예상되는 시간이다.
   2. 주어진 mid 시간 동안 각 심사위원이 심사할 수 있는 인원수를 모두 더한다.
   3. check 값이 심사 대상수보다 많다면 mid 값을 줄인다.
   4. 그렇지 않다면 mid값을 늘린다.
3. 전부 수행하고나면 left에 target의 값이 저장되어 있다. (target = 심사가 끝나는 최소 시간)

 

이분 탐색의 알고리즘이라는 맥락은 동일하지만, 구하려는 값(target)을 무엇으로 설정할지에 대해 어려움을 겪었던 문제이다.