이번 문제는 유니온 파인드를 이용하여 해결하였다. 처음에는 gate리스트를 만들고, 비행기 순회하며 gate를 뒤부터 확인하며 도킹할 수 있는 gate에 도킹하도록 하는 방식으로 풀이하였다. 답은 잘 도출되었지만, G와 P의 범위가 10^5이기 때문에 시간초과가 날 수 밖에 없었다.

다른 방법이 도저히 생각나지 않아 다른 사람의 코드를 보게 되었고, 유니온 파인드를 통해 해결한 것을 볼 수 있었다. 처음에는 코드가 잘 이해되지 않아 한줄 한줄씩 따라가며 코드를 분석하였다.

여기서의 아이디어는 자기 자신을 부모로 가지는 parent리스트를 생성하고, 숫자가 들어오면 그 숫자에 해당하는 부모를 찾은 후, 부모를 바로 밑 번호에 이어주는 것이다. 이렇게 되면 해당 번호의 부모가 1~i까지 도킹되지 않은 가장 큰 번호를 가지게 된다.

Code

처음 풀이 (시간 초과)

g = int(input())
p = int(input())
airplane = [int(input()) for _ in range(p)]
gate = [False for _ in range(g+1)]
answer = 0
for i in range(p):
    chk = False
    for j in range(airplane[i], 0, -1):
        if not gate[j]:
            gate[j] = True
            chk = True
            answer += 1
            break
    if not chk:
        break
print(answer)

유니온-파인드 풀이

g = int(input())
p = int(input())
airplane = [int(input()) for _ in range(p)]
parent = [i for i in range(g+1)]
answer = 0
def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]
for i in range(p):
    tmp = find(airplane[i])
    if tmp == 0:
        break
    parent[tmp] = parent[tmp-1]
    answer += 1
print(answer)