백준 10775번: 공항 (파이썬)

https://www.acmicpc.net/problem/10775

10775번: 공항

 

문제

 

오늘은 신승원의 생일이다.

 

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

 

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

 

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

 

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

입력

 

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)가 주어진다.

 

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)가 주어진다.

 

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

 

출력

 

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

풀이

 

비행기를 최대한 gi 게이트에 가깝게 도킹하도록 한다.

처음에는 리스트를 사용하여 시간 초과 문제가 발생하였고, 구글링 끝에 union find 문제라는 것을 알게 되었다.

알고리즘 수업 시간에 배웠던 기억이 났는데, 실제로 구현은 처음 시도해 보았다.

 

parent라는 disjoint set을 만든다. 각 비행기가 gi 게이트에 도킹되도록 초기화 한다. 이때 break 조건을 위해 0:0까지 포함하는 것이 중요하다.

find_parent 함수는 parent disjoint set에서 parent를 찾아주는 함수다.

union은 x의 parent를 y의 parent로, 즉 parent를 합치는 함수다.

 

이후 각 비행기의 gi를 확인하고, parent를 찾아 해당 게이트에 도킹되도록 한다.

이때 parent가 0이라는 것은 가능한 게이트가 없다는 뜻이므로, break한다.

정상적으로 해당 게이트 도킹이 되었다면 해당 게이트와 해당 게이트 - 1를 union 하고 횟수를 1 올린다.

 

소스 코드

 

import sys

def find_parent(x):
    if x == parent[x]:
        return x
    p = find_parent(parent[x])
    parent[x] = p
    return p

def union(x,y):
    x = find_parent(x)
    y = find_parent(y)
    parent[x] = y

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

gi = []
for i in range(p):
    gi.append(int(sys.stdin.readline()))

parent = {i:i for i in range(g+1)}

cnt = 0
for i in range(p):
    x = find_parent(gi[i])
    if x == 0:
        break
    union(x, x-1)
    cnt += 1
print(cnt)