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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

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

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

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

출처: 프로그래머스

---

처음에는 최소공배수 문제인 줄 알았다. 하지만 심사관의 수가 변화할 수 있는데다가 심사 시간이 너무 크고, 무엇보다 기다렸다가 다른 사람한테 받는 경우가 더 빠른 경우도 있어서 아니라는 것을 알 수 있었다.

 

결국 이 문제는 이분탐색 문제였는데, 내가 이분탐색을 많이 연습하지 않아 접근하기 힘들어 결국 질문하기의 도움을 받아 풀 수 있었다.

 

<정답 코드>

def solution(n, times):
    answer = 0
    
    min_t = times[0]
    max_t = times[0] * n
    
    while True:
        mid = (min_t + max_t) // 2
        cnt = 0
        
        for i in times:
            cnt += mid//i
        
        if cnt < n:
            min_t = mid
        
        elif cnt >= n:
            max_t = mid
        
        if min_t == max_t - 1:
            answer = max_t
            break
        
    return answer

접근은 아래와 같다.

주어진 times 배열은 오름차순으로 정렬된 배열이라는 가정을 포함한다. (⬅ 문제 내에서 제시된 사항은 아니지만, 주어진 테스트 케이스는 위 가정을 모두 만족하였다.)

1. 입국심사가 가장 빠르게 끝날 때는 가장 빠른 심사관 한명에게 한명이 심사 받는 시간이므로 times[0], 가장 오래 걸린다하더라도 가장 빠른 심사관이 n명을 모두 점검하는 시간이므로 times[0] * n 을 각각 변수로 저장한다.
2. 이 두 변수를 가지고 이분탐색을 시작한다.
   1. mid 시간을 소요했을 때 심사 받은 사람의 수는 mid 시간에서 각 심사관의 소요 시간을 나눈 몫만큼이다.
   2. 통과한 사람의 수가 n보다 작다면 mid가 증가하는 방향으로 가야하므로 min_t를 mid로 업데이트 한다. 반대로 n보다 크다면 mid가 감소해야 하므로 max_t를 mid로 업데이트 한다.
   3. 결과적으로 정확히 n명을 통과하는 시간 중 최단 시간을 출력해야하므로 n == cnt라도 계속해서 시간을 줄여가면서 탐색한다.
   4. 최종 탐색 결과는 min_t와 max_t가 1만큼 차이날 때가 되므로 이 때의 시간을 출력한다.

 

이분탐색 문제는 원래 난이도가 높기도 하고 다른 문제들에 비해 문제 수도 많지 않아서 연습이 덜 되어 있었다. 이번 문제로 배열 안에서 필요한 시간을 도출하는게 아닌, 외부 조건을 도입하면서 이분 탐색을 하는 방법을 배울 수 있어서 좋았다.