(Python) - 프로그래머스 : 입국심사

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

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

 

• 해설 :

입국심사관들이 입국심사하는데 걸리는 시간들이 담긴 배열과 입국심사를 받아야 하는 사람의 수 n이 주어질 때, 모든 사람을 입국심사하는데에 걸리는 최소 시간을 찾는 문제이다.

 

 

 

• 풀이 :

이분 탐색(Binary Search) 문제이다. 너무 어려웠다. 처음 봤을 땐 이분 탐색을 사용해야겠다는 생각은 1도 들지 않았고 그리디, 또는 브루트포스를 사용하여 모든 경우를 탐색하는 방법으로 구현하려 하였다. 하지만, n의 범위가 최대 10억이기 때문에 시간초과가 무조건 나는 상황이었다.  다른 사람의 풀이를 참조하여 해결하였는데 

풀이과정은 

1. 0부터 가장 시간이 많이 걸리는 심사관 * n의 값을 이분탐색의 범위로 잡는다.

2. mid값을 계산하고 이 값 내에 모든 사람을 계산할 수 있는지 확인한다. 

3. 계산할 수 없다면 left값을 mid+1로 바꾸고 없다면 right를 mid값으로 바꾼다.

이 로직을 구현하면 된다.

풀이과정을 알면 정말 쉬운 문제이지만, 문제를 보고 풀이과정을 떠올리는 것이 엄청나게 어려운 문제였다.

 

 

 

 

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n
    while left < right:
        tmp = 0
        mid = (left+right) // 2
        
        for time in times:
            tmp += mid//time
        if tmp >= n:
            right = mid
        else:
            left = mid + 1
    answer = left
    return answer