[Python] 백준 10775번 (공항)

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

---

풀이 방법

• 비행기가 오는 순서대로 게이트에 넣어야 함.

틀린 코드

import sys

g = int(sys.stdin.readline().rstrip())

p = int(sys.stdin.readline().rstrip())

count = 0

gate_list = [0 for _ in range(g)]
plane_list = []
for i in range(p):
    plane_list.append(int(sys.stdin.readline().rstrip()))

# 비행기가 순서대로 도착하는데 도킹못하면 폐쇄됨.
for i in plane_list:
    p_idx = i-1
    if sum(gate_list) == len(gate_list):  # 게이트에 비행기가 가득찬 경우 종료
        break

    if gate_list[p_idx] == 0:  # 비행기 번호에 맞는 게이트가 비어있으면 집어넣는다.
        gate_list[p_idx] = 1
    else:  # 비행기 번호에 맞는 게이트가 이미 채워져 있다면
        for j in range(p_idx, -1, -1):  # 최대한 큰 번호의 게이트에 비행기를 넣는다. (비행기 번호보다는 작거나 같은 게이트여야 함)
            if gate_list[j] == 0:
                gate_list[j] = 1
                break
            break

print(sum(gate_list))
#print("도착한 비행기 순서", plane_list)
#print("게이트: ", gate_list)

이렇게 비행기가 들어가는 게이트를 하나씩 찾아가게 풀면 시간초과가 난다...

비어있는 게이트를 찾는 시간을 줄이기 위해 Union-Find 알고리즘을 사용해야 한다.

import sys

g = int(sys.stdin.readline().rstrip())

p = int(sys.stdin.readline().rstrip())

count = 0

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

#게이트는 처음 자기자신 값을 가짐 ex) g= 4 인 경우 [0, 1, 2, 3, 4]
gate_parent = [i for i in range(g+1)]


def find(plane):
    # 게이트가 자기 자신을 가르키는 경우 == 게이트가 비어있음
    if gate_parent[plane] == plane:
        return plane
    gate_parent[plane] = find(gate_parent[plane])
    return gate_parent[plane]

for plane in plane_list:
    temp = find(plane)
    if temp == 0:
        break
    gate_parent[temp] = gate_parent[temp-1]  #게이트가 채워졌으므로 옆의 게이트로 부모 게이트를 바꿔줌
    count += 1

print(count)