[Python] 백준 10775 공항

 

 

문제

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

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

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

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

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

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

 

 

 

 

 

난이도

골드 2

 

 

 

 

 

내 코드

import sys

def find(x) :
    if parent[x] != x :
        parent[x] = find(parent[x]) # 최적화
        return parent[x]
    return x

def union(a,b) :
    a = find(a)
    b = find(b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b
 
G = int(sys.stdin.readline())
P = int(sys.stdin.readline())
parent = [i for i in range(G+1)]
cnt = 0
for _ in range(P) :
    gate = int(sys.stdin.readline())

    find_gate = find(gate)
    if find_gate == 0 :
        break

    union(find_gate,find_gate-1)
    cnt += 1

print(cnt)

 

 

 

 

 

 

풀이과정

처음 생각했던 로직은 일단 게이트 번호가 들어오면 해당 번호에 넣거나 해당 번호의 게이트가 차 있으면 그 전 번호의 게이트에 도킹시키는 로직이었다. 이렇게하니 28% 에서 시간초과가 걸렸다.

 

유니온-파인드로 해서 풀 수 있었다. find() 함수로 해당 게이트의 연결된 최상위 게이트를 찾아서 거기에 비행기를 도킹 시키고, 도킹 시켰으면 그 게이트와 그 전 게이트를 union()을 사용해 다시 이어두는 방법을 이용하였다. find() 했을 때 0이 나온다는 뜻은 1번 부터 해당 게이트까지 꽉 찼다는 소리이므로 count 를 중단 시키고 출력한다.