문제
공항에는 G개의 탑승구가 있다. (1~G), 공항에는 P개의 비행기가 도착할 예정이며
i번째 비행기는 1번부터 g번째(1<=g<=G) 탑승구 중 하나에 영구적으로 도킹하여야 한다.
이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있다. 또한, P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도
도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지한다. 최대한 많은 비행기를 공항에 도킹하고자 할 때,
최대 몇대의 비행기를 도킹할 수 있는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 G, 둘째 줄에는 P, 다음 P개의 줄에는 g가 주어짐
출력
도킹할 수 있는 비행기의 최대 개수를 출력
parent 리스트의 원소를 기둥으로 생각하면,
두 원소가 union된 경우 그 사이의 gate에 비행기가 들어온 것으로 간주할 수 있다.
가장 우선적으로 채워야 하는 gate를 find_parent로 빠르게 찾아 낼 수 있으며 find_parent의 리턴값이 원소 0이라면
입력된 숫자보다 작은 gate는 모두 비행기가 도킹되어 있는 상태이므로 종료하면 된다.
풀이
# 18-42) 탑승구
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a > b: parent[a] = b
else: parent[b] = a
g = int(input()); p = int(input()); cnt = 0
parent = [i for i in range(g+1)]
for _ in range(p):
airplane = int(input())
gate = find_parent(parent, airplane)
if gate == 0: break
else: union(parent, gate, gate-1); cnt += 1
print(cnt)