[BOJ] 10775번 - 공항

백준 10775번 - 공항

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	8942	3098	2312	37.016%

문제

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

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

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

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

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

 

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ ${10^5}$)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ ${10^5}$)가 주어진다.

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

 

출력

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

---

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

출처

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

10775번: 공항

알고리즘 분류

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

접근 방법

먼저 가장 Naive한 방법으로 접근을 해본 다음, 최적화 할 수 있는 부분들을 살펴보며 시간복잡도를 줄여보자.

Naive한 접근 방법

비행기의 수(P)개의 ${g_i}$를 입력을 받음과 동시에 1번째 게이트~${g_i}$번째 게이트 까지 탐색하며, 도킹 가능한 게이트에 도킹을 시키는 방식이다. 단, "도킹시킬 수 있는 최대의 비행기 수"를 구하기 위해 도킹 가능한 게이트들의 집합이 ${ {s_1, s_2, s_3, ..., s_k} }$ (단, ${s_k < s_{k+1}}$)라고 가정을 하였을 때, ${s_k}$에 도킹을 시키는 것이 도킹할 수 있는 최대의 비행기를 도킹하는 방법임을 알 수 있다. -> Greedy 한 접근

이 때, O(P*G)의 시간복잡도를 가지게 되고 문제에서 G와 P의 최댓값이 모두 ${10^5}$이므로 이러한 방식은 TLE인 것을 알 수 있다.

개선된 방법

각각의 비행기를 도킹할 수 있는 게이트를 찾기 위해 O(G)만큼 탐색시간이 소요되는 것을 개선해보자.

주어진 ${g_i}$ = k 라고 두었을 때, find(k)는 k보다 작거나 같은 게이트 번호 중 최댓값을 찾는 기능을 수행한다고 가정을 하였을 때

find(k)를 O(N) 미만으로 시간 복잡도를 줄이는 방법으로는 여러가지가 있겠지만, 경험적으로 트리형태의 자료구조를 활용해야한다는 것을 알 수 있다. 다음으로 K게이트에 도킹이 가능하여 도킹을 하고자 하는 상황일 때를 생각해보자. 

k게이트에 도킹을 한 후, 적절하게 k보다 작고 다음 도킹이 가능한 게이트 번호 중 최댓값을 찾아야한다. 이 과정을 _union이라고 가정을 한다. 앞서 가정한 find의 기능을 생각한다면 쉽게 _union의 기능을 구현할 수 있다.

k번째 게이트를 도킹한 후, k-1번째 게이트에 도킹이 가능하다면 이 번호를 메모하고 아니라면 k-1 보다 작은 게이트 번호 중 도킹이 가능한 최댓값 번호를 메모해야한다.

이렇게 대표 값을 O(1)에 근사하는 시간복잡도로 줄일 수 있는 자료구조로 Union-Find 자료구조가 있다.

2020.12.12 - [자료구조 + 알고리즘/기초] - 서로소 집합 ( Disjoint Set Unit ) 자료구조

서로소 집합 ( Disjoint Set Unit ) 자료구조

이러한 자료구조의 특징을 빠르게 캐치하여 응용하는 것이 매우 중요하다고 할 수 있다.

각각의 메소드는 다음과 같은 역할을 한다.

1. find(u) : u보다 작거나 같은 게이트 중 도킹이 가능한 게이트 번호의 최댓값
2. _union(k, k-1) : k게이트에 도킹한 다음, 다음 도킹이 가능한 게이트 번호 중 최댓값을 찾아 저장

find(gi)가 0이 되는 경우, 과정들에 의해 도킹가능한 게이트가 없다는 것이므로 반복문을 종료하고 출력한다.

 

유니온 파인드 자료구조의 특징에 따라 find와 union은 애커만 함수의 역함수만큼 시간복잡도가 소요되며 이는 O(1)와 근사하기 때문에 총 시간 복잡도는 O(P)에 근사한다고 볼 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
vector<int> airports;
int find(int u){
    if( u == airports[u] )
        return u;
    return airports[u] = find(airports[u]);
}
bool _union(int u, int v){
    // u > v 라는 것이 보장
    // union 과정에서 정의 상, 무작정 높이가 높아지지 않음
    // 또한, u -> v 의 단방향으로 union 되어져야함. union_by_rank를 이용한다면
    // 이러한 방향성이 사라지거나 모호해질 수 있다.
    u = find(u), v = find(v);
    if( u == v )
        return false;
    airports[u] = v;
    return true;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int G, P, ans = 0;
    cin >> G >> P;

    // airports[i] : i번째 게이트에 도킹하고자 할 때, 수용가능한 공항번호 중 최댓값
    // (단, i보다는 작거나 같아야함)
    airports.resize(G+1);
    // 초기 상태는 모든 게이트에 비행기가 도킹되지 않은 상태
    for(int i=1; i<=G; i++){
        airports[i] = i;
    }
    for(int i=0; i<P; i++){
        int gi;
        cin >> gi ;
        // int k = airports[gi]; 경로 압축이 되지 않은 부분도 존재할 수 있다.
        int k = find(gi);
        if( k == 0 )
            break;
        _union(k, k-1);
        ans += 1;
    }
    cout << ans ;
    return 0;
}