백준(10775) - 공항 Python

백준(10775) - 공항

문제유형 : 그리디 알고리즘, 파이썬

해결방법

이 문제는 이것이 취업을 위한 코딩 테스트다 의 문제 중 탑승구와 완전히 동일한 문제이다.

해설은 탑승구 페이지에서 확인하면 되겠다.

기출문제이다 보니 공통된 문제들이 종종 보이는 것 같다.

import sys
input = sys.stdin.readline


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

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

G = int(input())
P = int(input())
parent = [i for i in range(G+1)]

planes = []
for _ in range(P):
    planes.append(int(input()))

cnt = 0
for plane in planes:
    root = find(parent, plane)
    if root == 0:
        print(cnt)
        break
    else:
        union(parent, root, root - 1)
        cnt += 1