[백준 파이썬] 10775 공항

백준 10775

도킹할 수 있는 가장 높은 번호의 게이트부터 비행기를 도킹시킨다. 해당 인덱스에 도킹을 시켰다면 다음에는 그 인덱스보다 1 적은 값에 도킹시켜야하므로 이 인덱스를 저장해주어야한다.

G = int(input())
P = int(input())
gates = [int(input()) for _ in range(P)]

parent = list(range(G+1)) # 도킹 예정 리스트
def find(p): # 도킹 가능한 게이트
    if p == parent[p]:
        return p
    else:
        parent[p] = find(parent[p]) # 경로 압축
        return parent[p]

count = 0
for g in gates:
    idx = find(g) # 비행기가 도킹하려는 게이트 찾기
    if idx < 1: # 가능한 게이트 없다면 
        break # 종료
    parent[idx] = idx - 1 # 있다면 도킹 후 이 게이트로 들어온다면 이전 인덱스로 가도록
    count += 1 # 도킹한 비행기 수 추가
    
print(count)