BOJ 10775 - 공항

www.acmicpc.net/problem/10775

10775번: 공항

 

처음 이문제를 봤을때,

해시테이블을 써야되나 라고 생각했다.

그래서 c++ 의 unordered_map 을 사용해서 입력을 받을때마다 해당 인덱스를 value값으로 입력으로 주어지는 gi 값을 key 값으로 하는 그런 해시테이블을 만들어서 처리하는 문제인줄 알았다.

그러나 통과하지 못했고,

 

배열로 작성해서 이중포문 돌리는 것 역시 최댓값이 10^5 이므로 O(N^2) 이 되면, 시간초과가 나서 통과할 수 없었다.

 

#include <cstring>
#include <iostream>
 
#define MAX 100001
 
using namespace std;
 
int G, P, answer;
int arr[MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> G;
    cin >> P;
    
    memset(arr, -1, sizeof(arr));
    
    for (int i = 1; i <= P; ++i) {
        int g;
        cin >> g;
        
        bool flag = false;
        
        for (int j = g; j >= 1; --j) {
            if (arr[j] == -1) {
                arr[j] = i;
                flag = true;
                answer++;
                break;
            }
        }
        
        if (!flag) break;
    }
    
    cout << answer;
    
    return 0;
}

 

나중에 알고보니, 이 문제는 union-find 자료구조를 이용해서 풀어야 하는 문제였다.

 

- 참고 : blog.naver.com/kks227/220791837179

유니온 파인드(Union-Find) (수정: 2020-08-03)

 

i번째 게이트에 어떤 비행기를 도킹 시키면, 

union(gi, gi - 1) 을 해서 합쳐서 한쪽을 트리의 루트로 만들고,

다음 gi-1 번째도 도킹 할 수 있다고하면, gi-2 번째와 union 연산을 시킨다.

union(gi - 1, gi - 2) ....

이런식으로 쭉 합치다보면 하나의 트리가 만들어지는데

만약 도중에 루트가 0이되면, 더이상 도킹할 수 있는 자리가 없게 되는 것 이므로,

이때 프로그램을 종료시킨다.

 

- c++

#include <iostream>
 
#define MAX 100001
 
using namespace std;
 
int G, P, answer;
int arr[MAX];
 
int _find(int n) {
    if (arr[n] == n) return n;
    arr[n] = _find(arr[n]);
    return arr[n];
}
 
void _union(int a, int b) {
    a = _find(a);
    b = _find(b);
    arr[a] = b;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> G;
    cin >> P;
    
    for (int i = 1; i <= G; ++i) arr[i] = i;
    
    for (int i = 1; i <= P; ++i) {
        int g;
        cin >> g;
 
        int temp = _find(g);
        if (temp != 0) {
            _union(temp, temp - 1);
            answer++;
        } else 
            break;
    }
    
    cout << answer;
    
    return 0;
}