https://www.acmicpc.net/problem/10775
시간 1초, 메모리 256MB
input :
- 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10^5)
- 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10^5)
- P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.
output :
- 도킹시킬 수 있는 최대의 비행기 수를 출력
조건 :
- 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹
- 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
우선적으로 생각한 방법.
예제 2.
4
6
2
2
3
3
4
4
2, 2, 3, 3 을 입력받으면 게이트에 더이상 도킹을 할 수 없어 공항이 폐쇄됨.
그렇다면 가장 큰 숫자에서 부터 1까지 이 게이트에 도킹을 할 수 있는지를 판별하면 될 것 같다.
이중 for문을 사용하면 최악의 경우가 10^5 * 10^5 인데, 비행기 수가 10^5라면 시간이 터질 것 같다.
그렇게 해서 찾은 것이 union-find를 이용하는 것이다. 현재 도킹하려는 게이트가 0이아니라면 여전히 도킹이 가능 한 것으로, 게이트 마다 남은 자리를 표시하는 것이 아닌 게이트를 유동적으로 연결시켜 줄 수 있다.
맨 처음 비행기가 도킹하려는 게이트의 값이 0이 아니라면 더 이상의 비행기는 도킹이 불가능 하다.
그러면 가능 하다면 현재 비행기가 도킹하려는 게이트의 parent를 찾아 게이트의 parent - 1에 union하자.
2번 게이트에 도킹을 하면, 그 다음엔 1번 게이트에 도킹을 할 수 있으니까 이를 나타내기 위함이다.
import sys
def union(a, b):
# a번 게이트에 도킹을 하면 그 게이트에 다음 비행기가 오면
# 이것은 a - 1번 게이트에 도킹을 하게 된다.
# 이를 모든 배열에 적용시키기 위해 union-find를 사용.
parent_a = find(a)
parent_b = find(b)
data[parent_a] = parent_b
def find(x):
if x == data[x]:
return x
data[x] = find(data[x])
return data[x]
g = int(sys.stdin.readline())
p = int(sys.stdin.readline())
ans = 0
data = [i for i in range(g + 1)]
for i in range(p):
gate = int(sys.stdin.readline())
where = find(gate)
# 현재 gate에 도킹이 가능한가를 판별해야함.
# 이 gate의 부모가 0에 존재한다면 더 이상 도킹이 불가.
if where == 0:
break
union(where, where - 1)
ans += 1
print(ans)게이트의 수를 기준으로 data를 만들어야 하는데 비행기의 수를 기준으로 만드는 바람에 런타임 에러가 발생했다.
