[백준][C++] 10775 공항

www.acmicpc.net/problem/10775

10775번: 공항

 

 

 

알고리즘 종류

자료구조

분리집합(Union-Find)

 

 

 

사고 과정

무식하게 하게 2중 for문으로 하면 시간복잡도가 N^2이 나온다. 따라서 다른 방법을 사용해야 한다.

 

gi가 주어지면 gi부터 넣는 것이 빠르게 처리된다. 그리고 이후 -1씩 감소하면서 빈 곳을 찾으면 된다. 그렇다면, gi를 기준으로 왼쪽에 빈 곳이 있는 지 한 번에 알 수 있을까? 분리 집합을 이용하면 된다.

 

위 이미지를 보면, 5와 6은 2를 부모로 가리키고 있다. 4와 7 그리고 3은 0을 부모로 가리키고 있다. 이를 배열로 표현하면 아래와 같다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
 
int n, p;
int ans = 0;
 
vector<int> parents;
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);                                               
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> p;
    
    parents.resize(n+1);
    for(int i=0; i<=n; i++) parents[i] = i;
    
    int num;
    for(int i=0; i<p; i++){
        cin >> num;
        
        int parent = get_parent(num);
        
        if(parent == 0) break;
        
        parents[parent] = parent - 1;
        ++ ans;    
    }
    
    cout << ans << endl; 
}

 

 

 

시행착오