Baekjoon 10775. 공항 / Python

10775. 공항

난이도 : 골드 2
소요 시간 : 15분
날짜 : 2024.12.28
언어 : 파이썬
알고리즘 유형 : 그리디, 분리집합

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. G개의 게이트와 P개의 비행기가 있다.
2. 비행기를 게이트에 도킹해야 한다.
3. $g_i$가 입력으로 주어지고, 1 ~ $g_i$ 의 게이트에 i번 게이트를 도킹해야한다.
   • 게이트에 도킹을 할 수 없으면 끝
4. 도킹 수의 최댓값을 구하자.

2. 해결 방식

union-find 알고리즘을 사용한다.
- 게이트에 각자의 게이트 번호를 부여한다.
- 비행기번호를 union-find를 통해 게이트 집합을 만들어 관리한다.

3. 정답 코드

import sys

sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")
# input = sys.stdin.readline

g, p = int(input()), int(input())

planes = [int(input()) for _ in range(p)]
gates = [i for i in range(g + 1)]

def sol(plane):
    if gates[plane] == plane:
        return plane
    gates[plane] = sol(gates[plane])
    return gates[plane]

res = 0
for i, plane in enumerate(planes):
    docked = sol(plane)
    if not docked:break
    gates[docked] = gates[docked - 1]
    res += 1
print(res)