[프로그래머스] 입국심사 파이썬 풀

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

프로그래머스

---

1. 접근 방식

• 입국 심사를 시작하는 시간이 아니라, 끝나는 시간을 기준으로 생각하자

처음에 시작할 때는 0분이고, 모든 심사관이 비어 있으므로 한꺼번에 사람이 들어갈 수도 있고 더 빨리 끝나는 사람 뒤에 기다릴 수도 있다. 예를 들어 입국 심사에 1분 걸리는 심사관과 10분 걸리는 심사관이 있고, 심사 받을 사람이 5명이라면 5명 모두 1분 걸리는 심사관 쪽에 줄을 설 테다. 이걸 코드로 작성하려면 어떡할까? ... 시작하는 시간으로 심사 받을 사람을 제외하면 계산하기 어렵다.

따라서 분마다 심사가 끝난 사람을 세는 것이 더 쉽다. 1분이 지날 때마다 심사가 끝나는지 확인하자.

 

 

위 문제의 예제 데이터로 얘기하면, 입국 심사를 시작한 지 7분이 지났다면 1명, 10분이 지나면 2명, 14분이 지나면 3명, 20분이 지나면 4명, 21분이 지나면 5명, 28분이 지나면 6명이 끝난다. 이 패턴이 보이는가? 각 시간마다 심사관이 심사를 끝낸 인원은 (지난 시간 // 심사하는 데 걸리는 시간)이다.

 

 

• n명의 사람을 심사하는 데 걸리는 최소 시간을 알아내기 위해 이진 탐색을 사용하자

위에서 패턴을 찾았으니, 이제 심사하는 데 걸리는 최소 시간을 탐색해야 한다. 탐색 시간이 최대 10억이다. 수가 무척 크므로, O(log N) 시간 복잡도를 갖는 이진 탐색을 활용하여 최소 시간을 찾아보자.

심사하는 데 걸리는 최대 시간은 가장 심사하는 데 오래 걸리는 사람이 모든 n명의 사람을 심사하는 것이다. 따라서 right = max(times) * n으로 설정하고, left = 0으로 둔 채 이진 탐색을 시작한다. mid = (left + right) // 2는 현재 지난 시간이므로, (mid // times 리스트의 각 원소)를 합한 결과가 n명보다 많거나 같은지 체크하며 left와 right 값을 조정해나간다.

 

 

 

2. 정답 코드

def solution(n, times):
    l = 0
    r = max(times) * n
    answer = 0
    
    while l <= r:
        mid = (l + r) // 2
        
        people = sum(map(lambda x: mid // x, times))
        
        if people >= n:
            answer = mid
            r = mid - 1
        else:
            l = mid + 1
            
    return answer