백준|10775번|공항

문제 설명

G개의 게이트에 P개의 비행기를 순서대로 도킹시키려고 합니다. 각 비행기는 번호를 가지고 있고 비행기의 번호보다 작거나 같은 번호를 가진 게이트에만 도킹할 수 있습니다. 만약 비행기가 도킹할 수 없는 상황이 발생하면 즉시 모든 작업을 중단한다고 할 때, 최대 몇 대의 비행기가 도킹할 수 있는지 구하는 문제입니다.

작동 순서

1. 게이트의 개수와 비행기의 개수를 입력받습니다.
2. g번의 비행기가 왔을 때 도킹할 수 있는 게이트의 번호를 나타내는 배열을 생성합니다. 이때 도킹하는 게이트는 가능한 게이트 중 가장 번호가 높은 게이트입니다.
3. 비행기의 번호를 하나씩 입력받으며 find 연산을 통해서 도킹할 수 있는 곳을 찾습니다. 만약 find 연산을 수행한 결과 0이 나오면 비행기가 도킹할 수 없는 상황이므로 작업을 중단합니다.
4. 비행기의 도킹을 수행한 경우 union 연산을 통해서 게이트의 상황을 갱신해줍니다.
5. 도킹 가능한 비행기의 수를 출력합니다.

소스코드

import sys


def union(A, B):
    a = find(A)
    b = find(B)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def find(A):
    if parent[A] == A:
        return A
    parent[A] = find(parent[A])
    return find(parent[A])


G = int(sys.stdin.readline())
P = int(sys.stdin.readline())
parent = [i for i in range(G+1)]
count = 0
for i in range(P):
    num = int(sys.stdin.readline())
    if find(num) == 0:
        break
    count += 1
    union(num, find(num)-1)
print(count)