[BOJ 10775] 공항 (Python)

문제

공항

---

문제 해설

처음에 문제가 잘 이해되지 않아 시간이 걸렸는데, 비행기가 주어지면 1~i번 게이트까지는 자유롭게 도킹할 수 있는데, 비행기가 p만큼 들어오면 비행기를 최대한 많이 도킹시키는 것이 목표입니다.

비행기가 들어오면 도킹할 수 있는 게이트의 가장 높은 번호로 도킹을 시도합니다. 하지만 이 방식으로 하면 최악의 경우 1부터 게이트의 끝을 비행기의 개수만큼 조사해야 하기 때문에 당연히 시간초과가 납니다.

다른 방식을 생각하거나, 게이트를 고르는 방법을 바꾸던가 해야합니다.
저는 게이트를 고르는 방법을 완전탐색 -> Union-Find로 바꾸는 방법을 채택했습니다.

1. 자기 자신을 부모로 갖는 리스트를 생성합니다(parent)
2. 숫자가 들어오면 그 숫자에 해당하는 부모를 찾습니다.
3. 부모를 바로 밑 번호에 이어줍니다.

이렇게 구현하면 해당 번호의 부모가 1 ~ i까지 도킹되지 않은 가장 큰 게이트 번호를 갖는 구조가 됩니다.

여기서 주의할 점은 경로 압축을 통해 find메소드를 작성해야 한다는 점입니다.
경로 압축을 하지 않으면 최악의 경우 5 -> 4 -> 3 -> 2 -> .. 이런식으로 재귀의 깊이가 깊어질수 있기 때문에 N의 시간이 소요됩니다.

경로 압축을 하면 a(N)의 아커만 함수만큼의 시간이 걸립니다.
아커만 함수는 N이 2^65536 일 때 값이 5입니다.

---

풀이 코드

import sys

input = sys.stdin.readline
answer = 0
g = int(input())
p = int(input())
parent = [i for i in range(g + 1)]
planes = []

for _ in range(p):
    planes.append(int(input()))


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


for plane in planes:
    docking = find(plane)
    if docking == 0:
        break
    parent[docking] = parent[docking - 1]
    answer += 1
print(answer)

---