[Programmers] - 입국심사 (이분탐색) with Python

📎 간략한 문제 정리

• n명의 사람이 입국심사를 위해 줄을 서서 기다리고 있습니다. 심사관마다 심사하는데 걸리는 시간이 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하려고 합니다. 모든 사람이 심사를 받는데 걸리는 시간의 최소값을 return하는 함수를 작성합니다.

📈 문제 분석

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 또한 심사관은 1명 이상 100,000명 이하이고, 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분이하입니다. 시뮬레이션으로 각 상황을 그리며 결과를 비교하면 시간초과가 발생할 수 밖에 없는 범위입니다. O(N)만 되도 시간 초과가 발생합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 이렇게 기본 범위가 속도 이슈가 발생할 수 없는 경우일 때는 대다수의 경우 이분탐색을 활용합니다. 이분 탐색에서 포인트는 탐색할 기준이 무엇인지입니다. 예를 들어, 시간일 수도 있고 사람 수 일 수도 있습니다.

💻 풀이한 코드

def solution(n, times):
    slowest, latest = min(times), max(times) * n
    sec = 0
    while slowest <= latest:
        mid = (slowest + latest) // 2
        possible_people = 0
        for time in times:
            possible_people += (mid//time)
            if possible_people >= n:
                break
        if possible_people >= n:
            sec = mid
            latest = mid - 1
        else:
            slowest = mid + 1
    return sec

📝 해결 과정에서 만난 문제, 고민들

• 이분 탐색의 기준: 이 문제에서 가장 중요한 포인트는 이분 탐색의 기준을 어떤 것으로 설정할지 입니다. 처음 생각으로 주어진 범위를 활용하여 입국 심사를 기다리는 사람 수, 심사관이 한 명을 심사하는데 걸리는 시간, 심사관의 수 중 하나를 기준으로 정해야한다고 생각 했습니다. 하지만 포인트는 소요 시간을 기준점으로 잡는 것이었고 그 범위는 최대, 최소 시간을 직접 상정하여 범위를 만드는 것이었습니다. 최대 시간은 가장 오래걸리는 심사관이 모든 사람의 업무를 진행하는 것이므로 max(times) * n 이지만 최소 시간은 이와 같은 방식으로 진행할 수 없었습니다. 같은 방식으로 min(times) * n 이면 결국 한사람이 모든 일을 하는 경우로 심사관들이 일을 나눠서 할 경우 시간이 더 줄 수 있기 때문에 최소를 보장할 수 없습니다.

  다른 사람들의 풀이에서는 1로 최소시간을 설정한 경우가 많았지만 생각해보면 최소 시간은 절대 min(times) 보다 작을 수 없습니다. 경우에 따라서는 1과 큰 차이가 안날 수 있지만 min(times)와 max(times)의 차이가 작을수록 검색 범위가 축소되므로 저는 1이 아닌 min(times)를 최소 시간으로 설정했습니다. min(times)가 검색 시간이 될 수 있는 경우는 대기자가 한명인 경우입니다.

• 이분 탐색의 경우 답으로 계산해야하는 대상이 이분 탐색의 기준이 되는 경우가 많습니다.

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