백준 10775번 공항(C++)🚩🚩

71% 시간초과 

#include<vector>
#include <iostream>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int g,p;
    
    cin>>g;
    cin>>p;
    vector<int>gate;
    gate.assign(g+1,0);
    int t;
    
    int cnt=0;
    
    for(int i=0;i<p;i++){
        cin>>t; //1~t까지만 가능 
        bool flag=false;
        for(int j=t;j>=1;j--){
            if(gate[j]==0){
                gate[j]=1;cnt++;flag=true;
                break; 
            }
        }
        if(!flag)break;
        
    }
    
    cout<<cnt;
    
    return 0;
}

 

유니온 파인드로 갈수 있는 게이트 탐색을 구현한다.

find를 압축해서 구현 할경우 시간복잡도가 상수라고 한다..

#include<vector>
#include <iostream>

using namespace std;

vector<int>parent;

int find(int node){
    
    if(parent[node]<0)return node;
    
    return parent[node]=find(parent[node]);
    
}

bool unions(int x){
    
    int pg=find(x); 
    
    if(pg==0)return false;
    
    parent[pg]=pg-1;
    
    return true; 
    
}

//g...1 식으로 뒤에서부터 탐색, 처음 탐색하면 다음엔 이전 번호를 탐색하게 함
//따라서 어떤 곳 탐색할때 탐색할수 있는곳을 타고 타고 내려가게 됨 


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int g,p;
    
    cin>>g;
    cin>>p;
    vector<int>gate;
    gate.assign(g+1,0);
    parent.assign(g+1,-1);
    int t;
    
    int cnt=0;
    
    for(int i=0;i<p;i++){ //10^5
        cin>>t; //1~t까지만 가능 

        if(!unions(t))break;
        cnt++; 
    }
    
    cout<<cnt;
    
    return 0;
}