[BOJ 10775] 공항(Union-Find, Java)

## 접근

---

• 비행기를 최대한 많이 게이트에 도킹시키기 위한 방법은 입력으로 gi가 들어왔을 때, gi번째 게이트에서 1번 게이트까지 순차적으로 체크하면서 자리가 비면 넣어주면 된다. 
  * 역순으로 검사하는 이유는, 앞으로 등장할 수 있는 현재 gi보다 값이 작은 어떤 gi들에 대해서 게이트를 최대한 보장하기 위해서이다.
  
  
  
• gi번째에 비행기가 이미 도킹되어 있을 때, 역순으로 1번까지 검사하는 것은 시간복잡도가 초과한다(MAX : 10^5 * 10^5). 따라서, gi가 이미 도킹되어 있을 때, 넣을 수 있는 게이트를 바로 확인할 수 있도록 하는 방법을 찾아야 한다.
  
  
  
• 비행기를 도킹할 때, 다음 게이트를 가르킬 수 있도록 Union 연산을 사용하고, Find 연산을 통해서 경로압축최적화를 통해 O(1)만에 비행기를 넣을 수 있는 게이트를 바로 확인하도록 한다.
  
  
  
• Find 연산의 값으로 0이 나온다면, 비행기를 넣을 수 없으므로 종료한다.

 

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
public class Main{
    static BufferedReader br;
    static BufferedWriter bw;
    static int G, P, val;
    static int answer = 0;
    static int[] root;
    
    static int find(int x){
        if(root[x] == x)
            return x;
        else
            return root[x] = find(root[x]);
    }
    
    static void union(int x, int y){
        root[find(x)] = find(y);
    }
    
     public static void main(String []args) throws java.lang.Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        G = Integer.valueOf(br.readLine());
        P = Integer.valueOf(br.readLine());
        root = new int[G + 1];
        
        for(int i = 1; i <= G; i++) root[i] = i;
        
        for(int i = 1; i <= P; i++){
            val = Integer.valueOf(br.readLine());
            val = find(val);
            if(val == 0)
                break;
                
            union(val, val - 1);
            answer += 1;
        }
        
        
        bw.write(answer + "\n");
        bw.flush();
     }
}