[프로그래머스] 입국심사 - Python / 파이썬

문제 설명 

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항 

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

입출력 예

n	times	return
6	[7, 10]	28

---

문제 풀이

입국 심사 문제는 이분 탐색으로 해결하는 문제이다. 

이분 탐색으로 문제를 해결할 때에는

start와 end의 값을 어떻게 설정할지, 그리고 구하고자 하는 값(mid) 가 무엇인지 고려해야 한다.

 

문제에서 원하는 것은 모든 사람이 심사를 받는데 걸리는 시간이므로 

start와 end 그리고 mid 모두 시간에 관련된 변수라고 짐작할 수 있다. 

 

입출력 예시로 생각해보자면, 

1 2 3 4 5 6 

6명의 각 사람들이 2명의 심사관에게 입국심사를 받게 되고 각 심사관은 7분, 10분이라는 시간을 소요한다. 

따라서 한 심사관이 심사하는데에 걸리는 최소시간은 1분, 최대 시간은 10 * 6 = 60분이라는 것을 알 수 있다. 

즉, start = 1 / end = 60 으로 설정해야 한다는 사실을 알 수 있다.  

 

탐색할 범위를 정해주었으므로 mid 값을 계속 바꾸며 최종 답을 얻기만 하면 된다. 

그렇다면 mid값을 어떻게 계속 변경해주어야 할까?

이 부분이 가장 생각하기 어려웠다. 

 

일단 모든 각 심사위원이 mid 시간 동안 몇명의 사람을 심사할 수 있는지 확인해야 한다. 

코드에서 total += mid // time 부분이 이것을 확인하는 부분이다. 

만약 주어진 n명보다 많이 심사할 수 있다면 더 확인할 필요가 없으므로 즉시 탐색 범위를 바꾸도록 해준다. 

주어진 n명보다 많이 심사할 수 있다면 mid값을 더 줄여야 한다. 따라서 end를 mid - 1로 바꿔준다. 

이때, 시간의 최솟값을 구하는 것이므로 mid 값을 계속해서 저장해준다. 

반대의 경우 mid 값을 증가시켜줘야 하므로 start를 mid + 1로 바꿔준다. 

 

이렇게 계속해서 mid 값을 바꿔가며 탐색하면 모든 사람을 심사하는 데에 걸리는 최솟값을 구할 수 있다.

---

My Code

def solution(n, times):
    answer = 0
    
    max_value = max(times)
    start, end = 1, max_value * n
    
    while start <= end:
        mid = (start + end) // 2 
        total = 0
        for time in times:
            total += mid // time 
            if total > n:
                break 
        
        if total >= n:
            end = mid - 1
            answer = mid
        else:
            start = mid + 1
        
    return answer