[Gold II] 공항 - 10775

문제 링크

성능 요약

메모리: 36264 KB, 시간: 140 ms

분류

자료 구조, 그리디 알고리즘, 분리 집합

문제 설명

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 g_i (1 ≤ g_i ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 10⁵)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 10⁵)가 주어진다.

이후 P개의 줄에 g_i (1 ≤ g_i ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

---

문제 풀이

문제 분석

이 문제는 공항에 G개의 게이트가 있고 P개의 비행기가 순서대로 도착할 때, 각 비행기를 1번부터 g_i번 게이트 중 하나에 도킹시켜 최대한 많은 비행기를 도킹시키는 문제입니다. 만약 비행기를 도킹할 수 있는 게이트가 없다면 공항이 폐쇄되고 더 이상 비행기를 도킹할 수 없습니다. 입력은 게이트 수 G, 비행기 수 P, 그리고 각 비행기가 도킹할 수 있는 최대 게이트 번호 g_i로 주어집니다. 출력은 도킹할 수 있는 최대 비행기 수입니다.

접근 방법

이 문제는 그리디 알고리즘과 분리 집합(Disjoint Set Union) 자료 구조를 사용하여 해결할 수 있습니다. 각 비행기가 도착할 때마다 해당 비행기가 도킹할 수 있는 게이트 중 가장 큰 번호의 게이트에 도킹시키는 것이 최적입니다. 만약 해당 게이트가 이미 다른 비행기에 의해 점유되었다면, 분리 집합을 사용하여 해당 게이트의 부모 노드(다음으로 큰 사용 가능한 게이트)를 찾고, 그 게이트에 도킹시킵니다. 만약 부모 노드가 0이라면, 더 이상 도킹할 수 있는 게이트가 없으므로 공항을 폐쇄하고 종료합니다.

구현 설명

1. find(x) 함수 구현

• find(x) 함수는 분리 집합 자료 구조에서 특정 원소 x가 속한 집합의 대표(root) 노드를 찾는 함수입니다.
• 경로 압축(Path Compression) 기법을 사용하여 찾은 대표 노드를 parent[x]에 저장하여 다음 탐색 시 시간 복잡도를 줄입니다.

2. union(a, b) 함수 구현

• union(a, b) 함수는 분리 집합 자료 구조에서 두 개의 집합을 합치는 함수입니다.
• a와 b의 대표 노드를 찾은 후, a의 대표 노드의 부모를 b의 대표 노드로 설정하여 두 집합을 합칩니다.
• 문제의 맥락에서는 'a 게이트가 찼으니, b 게이트를 대신 사용한다'라는 의미로 해석할 수 있습니다.

3. 메인 로직 구현

• 게이트의 수 G와 비행기의 수 P를 입력받습니다.
• parent 리스트를 초기화합니다. 각 게이트는 처음에는 자기 자신을 부모로 가지도록 설정합니다 (자기 자신이 root).
• 각 비행기에 대해, 해당 비행기가 도킹할 수 있는 최대 게이트 번호 air를 입력받습니다.
• find(air) 함수를 사용하여 air 게이트의 대표 노드를 찾습니다.
• 만약 대표 노드가 0이라면, 더 이상 도킹할 수 있는 게이트가 없으므로 반복문을 종료합니다.
• 그렇지 않다면, union(x, x-1) 함수를 호출하여 air 게이트와 그 이전 게이트를 합칩니다. 이는 air 게이트가 찼으므로, 다음 비행기는 air - 1 게이트를 시도해야 함을 의미합니다.
• 도킹에 성공할 때마다 result 변수를 1씩 증가시킵니다.

4. 결과 출력

• 최대 도킹 가능한 비행기 수 result를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: 분리 집합의 find 연산은 경로 압축을 사용하므로 거의 O(α(n))의 시간 복잡도를 가집니다 (α(n)은 아커만 함수의 역함수로, 매우 느리게 증가하는 함수이므로 사실상 상수 시간으로 간주할 수 있습니다). union 연산도 O(α(n))입니다. 따라서 전체 시간 복잡도는 O(P * α(G)) ≈ O(P)입니다. 문제에서 P와 G의 최대 크기는 10⁵이므로, 충분히 빠른 시간 안에 실행됩니다.
• 공간 복잡도: parent 리스트는 G+1개의 원소를 가지므로, 공간 복잡도는 O(G)입니다.

핵심 포인트

1. 그리디 접근: 각 비행기에 대해 가능한 가장 큰 게이트에 도킹시키는 것이 전체적으로 최적의 해를 보장합니다.
2. 분리 집합 자료 구조 활용: 이미 점유된 게이트를 빠르게 찾고, 사용 가능한 다음 게이트를 효율적으로 탐색합니다. find 연산과 union 연산의 효율적인 구현이 중요합니다.
3. 경로 압축: 분리 집합의 find 연산에서 경로 압축을 사용하여 시간 복잡도를 최적화합니다. 경로 압축은 각 노드의 부모를 root 노드로 직접 연결하여, 다음 탐색 시 root 노드까지의 경로를 단축시킵니다.

풀이 코드

import sys

input = sys.stdin.readline

parent = {}
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    
    return parent[x]

def union(a,b):
    a = find(a)
    b = find(b)

    if a!=b:
        parent[a] = b

g = int(input())
p = int(input())

parent = [i for i in range(g+1)]

result = 0
for i in range(p):
    air = int(input())
    x = find(air)
    if x == 0:
        break
    union(x, x-1)
    result += 1

print(result)