[이것이 코딩테스트다] 탑승구

🗃️문제 설명

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1 ≤ gi ≤ G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다. 또한 P개의 비행기를 순서대로 도킹하다가, 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

첫째 줄에는 탑승구의 수 G (1 ≤ G ≤ 100,000)가 주어집니다.
둘째 줄에는 비행기의 수 P (1 ≤ P ≤ 100,000)가 주어집니다.
다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi (1 ≤ gi ≤ G)가 주어집니다.
이는 i번째 비행기가 1번부터 gi번째 (1 ≤ gi ≤ G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

🖥️코드

import sys
input = sys.stdin.readline

# 최대한 많은 비행기를 도킹시키기
# 작은 번호가 아닌 큰 번호 탑승구부터 도킹시켜야...
G = int(input())
P = int(input())
parent = [i for i in range(G+1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

answer = 0
for _ in range(G):
    g = int(input())
    data = find(g)  # 부모 노드를 찾기
    if data == 0:   # 0번 노드의 경우 도킹할 수 없다는 의미
        break
    union(data, data-1)
    answer += 1
print(answer)

🧠아이디어

알고리즘 유형 : 유니온 파인드

최대한 많은 비행기를 도킹하려면 작은 탑승구에 도킹하는 것이 아니라 인접하면서 큰 탑승구에 도킹하도록 해야 한다.

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 탑승구
모범 답안 - 탑승구