문제 설명

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

어떻게 문제를 풀 것인가

해당 문제는 이분 탐색을 이용해서 푸는 문제. 이분 탐색을 많이 접하지 않은 나로서는 이분 탐색의 대상을 걸리는 시간 이라고 생각하지 못해서 접근 조차 불가능했었다.

간략하게 설명하자면,

1. 입국심사를 받을 인원 n과 각 심사관이 심사에 걸리는 시간 times가 있다
2. 이에 대해 가장 최악의 경우 (모든 심사관이 가장 오래걸리는 심사관과 같은 시간이 걸린다고 가정하는 경우)를 최대값으로, 최적의 경우(모든 심사관이 가장 적게 걸리는 심사관과 같은 시간)을 최소값으로 초기화 한다
3. 현재 가능한 시간에 대해 현재 체크하려는 시간 값/각 심사관의 심사 시간을 모두 더한다. 이는 현재 주어진 시간에 대해 전체 심사관들이 총 처리 가능한 입국심사 인원의 수와 같다. (이하 sum)
4. 모두 더한 값이 n보다 크다면 현재 시간값이 최적의 값이 아니라는 의미이기 때문에 현재 시간의 절반의 상위 부분에 대해 다시 탐색, 작다면 그 반대 부분에 대해 탐색한다.

왜 어려웠는가

단순 이분탐색을 통해 sum == n이 되는 경우에 바로 답을 리턴하면 될 줄 알았으나... 문제에서 주어진 예시 n=6, times=[7, 10]의 경우 만약 값이 29가 되더라도 sum == n을 만족한다. 예시 입력에서는 걸리지 않았지만 테스트 케이스에서 빈번히 실패하여 결국 많은 블로그의 참고 끝에 잘못된 점을 파악했다.

파훼법(이라 할거까진 없지만)

sum < n인 경우에는 무조건 시간이 부족한것이니 늘려야 하지만 그 반대의 경우에는 sum == n일지라도 최적해는 아닌 경우가 있을 수 있으니 우선 답을 기록하고 다시 범위를 좁혀 탐색한다. 이분탐색의 탐색 조건이 종료되고 나면 그 답을 출력하면 된다.

def solution(n, times):
    answer = []

    start, end = n * min(times) // len(times), n * max(times) // len(times)
    mid = (start + end) // 2

    while start <= end:
        sum = 0
        mid = (start + end) // 2
        for time in times:
            sum += mid // time

        if sum < n:
            start = mid + 1
        else:
            answer = mid
            end = mid - 1

    return answer

TIL

• 이분탐색으로 찾은 결과가 항상 최적은 아닐 수 있음에 유의
• 이분탐색 자체에 대해서도 좀 정확히 알아야 할 필요가 있어보인다.