[BOJ 10775] 공항

문제

[BOJ 10775] 공항

구상1 (단순 그리디)

gi가 가장 큰 순으로 도킹할 수 있는 가장 큰 게이트에 도킹하면 되지 않을까? (그리디)
O(P*G)여서 시간초과!
구글링 해보니 union find로 풀 수 있다고 한다.

구상2 (union find)

코드

# Union find
# Union: gate에 비행기가 도킹한 경우 union_gates(gate,gate-1) 연산
# find: 해당 비행기가 도킹할 수 있는 게이트 찾기
import sys
input = sys.stdin.readline

def find_emptyGate(x): # find_parent
    if gates[x]!=x:
        gates[x]=find_emptyGate(gates[x])
    return gates[x]

def union_gates(a,b): # union_find
    a = find_emptyGate(a)
    b = find_emptyGate(b)
    if a<b:
        gates[b] = a
    else:
        gates[a] = b


G = int(input()) # 1<=게이트의 수<=10^5
P = int(input()) # 1<=비행기의 수<=10^5

gates = [i for i in range(G+1)]

cnt = 0
for p in range(P):
    maxGate = int(input())
    # 그냥 반복문 써서 도킹할 수 있는 게이트 찾으면 O(G) 걸리겠지만 
    # 서로소 집합 알고리즘 사용하면 O(1)에 가능
    enableGate = find_emptyGate(maxGate)
    if enableGate == 0:
        break
    # enableGate에는 p번째 plane이 들어갔으므로 
    # "enableGate-1부터 가능하다는 뜻"의 union_gates를 수행해줘야한다
    union_gates(enableGate,enableGate-1) 
    cnt += 1
print(cnt)

느낀점

나동빈님의 "이것이 취업을 위한 코딩테스트다"라는 책을 통해 union find 알고리즘을 공부해본적은 있지만, 이 문제에 union find가 어떻게 적용되는지 이해하기 쉽지 않았다.