탑승구 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 42, p 395

 

비행기를 '최대' 몇 대 도킹할 수 있는지 출력해야 하므로 이진 탐색을 이용해 풀이했습니다. 

먼저 도킹할 수 있는 비행기의 최소 대수를 1대, 최대 대수를 게이트의 개수인 G대로 설정합니다.

이후 중간값을 계산하고, 이 중간값만큼의 비행기를 도킹할 수 있는지 확인합니다.

비행기를 순서대로 도킹한다고 했으므로, 중간값 개수만큼의 도킹 정보를 가져오고, 이를 dock라는 함수에 전달합니다.

 

dock 함수는 도킹 정보 리스트를 받아 모든 비행기를 도킹할 수 있으면 True, 아니면 False를 반환하는 함수입니다.

이는 힙을 이용해 구현했는데, 파이썬의 heapq는 Min Heap이므로, Max Heap으로 사용하기 위해 각 element에 -1을 곱해줍니다. 이후 게이트의 최댓값을 pop해가면서 이 최댓값이 도킹해야할 비행기 대수보다 크거나 같으면, 비행기 대수를 1씩 감소시키고, 그렇지 않으면 바로 while문을 종료합니다.

while문을 종료했을 때 heap에 더 이상 도킹해야 할 비행기가 남지 않았으면 True, 남아 있으면 False를 반환합니다. 

 

중간값의 개수만큼 도킹할 수 있는 경우, answer에 현재 중간값을 저장하고, 더 많은 비행기를 도킹할 가능성도 있으니 중간값을 늘립니다.

중간값의 개수만큼 도킹할 수 없는 경우, 중간값을 줄입니다. 

 

import sys
import heapq

# 입력 받아오기 
inputs = list(map(int, sys.stdin.read().split()))
# 탑승구 개수
G = inputs[0]
# 비행기 개수 
P = inputs[1]
# 각 비행기의 도킹 가능 번호 
dockings = inputs[2:]

# 도킹 가능하면 True, 아니면 False 
def dock(dockings):
    # 도킹해야 할 비행기 개수 
    N = len(dockings)
    # max heap
    q = [(-1)*d for d in dockings]
    heapq.heapify(q)
    
    while q:
        max_gate = heapq.heappop(q)
        # 게이트 최댓값이 N 이상이면, 최댓값 게이트에 비행기 도킹
        if max_gate * (-1) >= N:
            N -= 1 
        else:
            break
            
    # 도킹해야 할 비행기가 남아있지 않으면 True, 남아 있으면 False 
    return True if len(q) == 0 else False   
    
    
# 최댓값: 탑승구 개수 
max_val = G
# 최솟값: 1 
min_val = 1 

answer = None 
# 이진 탐색 
while min_val <= max_val:
    mid_val = (min_val + max_val) // 2 
    # 도킹 가능하면 우선 answer에 현재 중간값 저장
    # 더 많은 비행기 도킹할 수 있는지 확인 
    if dock(dockings[:mid_val]):
        answer = mid_val
        min_val = mid_val + 1 
    # 도킹할 수 없으면 중간값 줄이기 
    else:
        max_val = mid_val - 1 

print(answer)