[PG/Python] 입국심사

📌 문제

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

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

 

📌 문제 접근 방법

1. 최소 시간을 구해야하므로 처음에는 최소힙을 이용해서 풀이하였다.
2. i를 현재 심사를 기다리는 사람의 번호라고 하면, 힙에 (i번째 사람의 심사가 끝날 시간, 심사관의 심사 시간)을 push해줬다.
3. 그 후 i를 계속 늘려가며 n이 될 때까지 힙에서 최소 시간을 pop하고 다시 걸린 시간만큼 더해서 push하는 작업을 반복한다. -> 이런 풀이의 경우 정답은 맞으나 6번에서부터 였나 시간초과가 발생한다.
4. 결국 문제의 분류에 맞게 이분탐색으로 풀이하였다.
5. left는 가장 적게 걸린 시간 (모든 심사관에게 1분만에 심사를 완료할 경우), right는 가장 오래 걸린 시간 (가장 오래 심사하는 심사관에게 모든 사람이 심사를 받을 경우)으로 초기화를 한다.
6. mid는 left와 right의 중간값으로 하고, mid분에 모든 심사관이 몇 명의 사람을 심사할 수 있는지 세어 cnt에 저장한다.
7. cnt가 n보다 크거나 같을 경우 right를 mid로 갱신하고, n보다 작을 경우 left를 mid+1로 갱신한다.
8. left가 right보다 작을 경우 계속해서 위의 시행을 반복하고 마지막엔 left를 반환해준다.

 

📌 코드

# heap 사용

def solution(n, times):
    heap = []
    for t in times:
        heapq.heappush(heap, (t, t))
    
    person = 1
    while person < n:
        endtime, time = heapq.heappop(heap)
        heapq.heappush(heap, (endtime+time, time))
        person += 1
    
    return heapq.heappop(heap)[0]

# 이진탐색 사용

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