틀린 코드

import sys
input = sys.stdin.readline

G = int(input())
P = int(input())
arr = [True]* G
g = []
ans = 0
for _ in range(P):
    g.append(int(input()))
    
for i in range(0,len(g)):
    req1 = g[i]
    sig=0
    for j in range(req1-1,-1,-1):
        if(arr[j]==True):
            arr[j]=False
            ans+=1
            sig=1
            break
    if(sig==0):
        print(ans)
        exit()

처음 생각한 코드입니다.

하지만 이 코드는 거의 brute force와 같아 시간 복잡도가 너무 높고 실제로 백준에 제출하였을 때도 시간초과가 나오게 되었습니다.

코드

import sys
input = sys.stdin.readline

def solve(n):
    if(reps[n] == n):
        return n
    reps[n] = solve(reps[n])
    return reps[n]

G = int(input())
P = int(input())
ans=0
reps = [i for i in range(G+1)] #게이트
for _ in range(P):
    n = int(input())
    a = solve(n)
    if(a== 0):
        break
    reps[a] = reps[a-1] #도킹을 하고 가장 큰 도킹 가능한 값으로 가야함
    ans+=1
print(ans)

위 코드는 유니온 파인드(Union-Find) 알고리즘을 사용한 방식입니다.

유니온 파인드는 분리집합이라고도 불리는데 이를 이용하여 시간 복잡도를 크게 감소시켰습니다.

후기 및 풀이

솔직히 이해하는데 시간이 꽤나 오래걸렸고 유니온 파인드라는 문제란 걸 알고 나서 그걸 문제 푸는데 접목시켜보려 했는데 그것도 실패하였다..

그래서 구글링하고 최대한 이해하는데 집중하였던 문제입니다.

게이트를 들어갈 때는 우선 들어갈 수 있는 가장 높은 번호의 게이트 먼저 들어가야 합니다.

위 문제 예제 1을 예시로 들어보겠습니다.

4 3 4 1 1

reps라는 배열을 (게이트 개수 + 1)의 크기만큼 만들어줍니다.

그럼,

reps [0] = 0

reps [1] = 1

reps [2] = 2

reps [3] = 3

reps [4] = 4

가 생성되었을 겁니다.

처음에 비행기 4 가 들어왔기에 4번 게이트에 넣어줍니다.

이제 4번 게이트에는 비행기가 들어오지 못하겠죠?

그러면 또 다른 비행기 4 가 들어온다고 해도 4번 게이트가 아닌 3번 게이트로 들어가게 됩니다.

여기서 유니온 파인드의 개념이 사용되게 되는 것입니다.

reps [4]의 값을 3으로 바꾸는 것입니다.

그럼 reps [0] = 0 , reps [1] = 1, reps[2] = 2, reps[3] = 3, reps[4] = 3이 되네요.

비행기 1 이 들어오면 [0 0 2 3 3]이 됩니다.

다음번 비행기 1 이 들어오면 reps[1] = 0 이므로 더 이상 비행기를 도킹시킬 수 없게 되는 것입니다.

즉 reps [n]의 값이 0이라면 답을 출력하면 되고 0이 아니라면 도킹이 가능한 비행기의 수를 1 증가시키는 것입니다.

p.s. 시간 복잡도 : O(P log G)