import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)
def findparent(x):
if parent[x] == 0:
return False
if gate[parent[x]] == 0:
return parent[x]
parent[x] = findparent(parent[x])
return parent[x]
G = int(input())
P = int(input())
gate = [0]*(G+1)
parent = {i:i-1 for i in range(1,G+1)}
result = 0
fail = False
for i in range(P):
g = int(input())
if fail:
continue
if gate[g] == 0:
gate[g] = 1
result += 1
else:
if findparent(g):
gate[findparent(g)] = 1
result += 1
else:
fail = True
print(result)
시간을 생각하지 않으면 그냥 이중for문 돌리면 되지만 그러면 시간초과가 나는 문제이다.
union-find 알고리즘을 통해서 해결하였다.
모든 게이트번호에 대해서 부모를 번호-1한 값으로 설정하고, 만약 게이트가 이미 차있으면 부모를 찾고, 경로압축을 하는 방식으로 시간초과를 해결하였다.
오늘의 교훈) union-find 알고리즘은 유용하다!