[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 입국심사

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

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

[문제 설명]

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

[제한 조건]

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

[아이디어]

1) 각 심사관이 걸리는 시간(times)의 원소들로 목표 시간을 나눈 몫의 합이 n이 되는 최소의 n을 구하면 된다.
- ex) 예시에서 28분이 가능한 이유는 28//7 + 28//10 = 6인 최소의 숫자이기 떄문이다.

2) 다만 제한 조건에서 n의 값과 times의 원소의 범위, 그리고 times의 length가 꽤 클 수 있다는 것을 생각했을 때, 이 일반적인 로직은 효율성 테스트를 통과하지 못할 확률이 크다.

3) 결국 목표로하는 시간을 일정 범위 내에서 찾아가도록 해야할 것 같다.

 

# 테스트케이스 1,2만 통과, 나머지는 시간초과
def solution(n, times):  
    answer = 0
    while True:
        answer +=1
        tmp = sum(map(lambda x: answer//x, times))
        if tmp == n:
            return answer

이것이 기본 로직인데, 당연하게도 시간 초과가 나왔다. 저 목표인 answer를 보다 효율적으로 찾아가는 로직이 필요하다.

# 정답
def solution(n, times):  
    low = 1
    high = min(times)*n
    while low != high:
        mid = (low + high) // 2
        tmp = sum(map(lambda x: mid//x, times))
        if tmp >= n:
            high = mid
        elif tmp < n:
            low = mid + 1
    return low

걸리는 최대의 시간을 정한 뒤, 해당 범위 내에서 정답을 찾아나간다. 이분탐색의 아이디어가 꼭 직접적인 탐색이 아니더라도 사용될 수 있음을 기억하면 될 것 같다. 이 문제에서는 특정 조건을 만족하는 숫자에 대한 탐색을 이분탐색의 아이디어를 적용하여 진행했다.