[백준] 10775 공항

✔️ 문제 링크

https://www.acmicpc.net/problem/10775

💡 핵심 아이디어

1️⃣ 번호가 큰 자리부터 먼저 채워 넣는다.

2️⃣ 만약 자신이 앉을 수 있는 가장 큰 번호의 자리가 차있다면 union-find알고리즘을 이용해 차선책으로 큰 자리수를 구하고 그 자리에 배정을 해 놓는다.

❗️오답 이유

1️⃣ 핵심 아이디어 2번 부분에서 다시 for문을 돌아 배정하려고 하였으나 데이터의 수가 $10^5$이라 시간초과로 인하여 실패

⭐️ 소스 코드

if __name__ == '__main__':
    G = int(input())
    P = int(input())
    p_list = [int(input()) for _ in range(P)]
    parent = [p for p in range(G+1)]

    def find(p):
        if parent[p] == p:
            return p
        parent[p] = find(parent[p])
        return parent[p]

    def union(a,b):
        a_parent = find(a)
        b_parent = find(b)
        parent[b_parent] = a_parent

    ans = 0
    for v in p_list:
        v_parent = find(v)

        if v_parent == 0:
            break

        ans += 1
        union(v_parent-1, v_parent)
    print(ans)