[JAVA] 백준 10775번: 공항

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

10775번: 공항

✅ 골드Ⅱ
 

🔶 풀이

브루트 포스 형식으로 알고리즘을 진행했더니 속도와 메모리면에서 전혀 효율적이지 못 했다.
구글링을 해보니까 Disjoint-Set (Union-Find) 알고리즘으로 해결한 분을 봤고, 그 분의 코드와 해설을 가져와봤다.
 

✔️ 예제 2번

게이트 수: 4개
비행기 수: 6개
비행기 도착 순서: 2 → 2 → 3 → 3 → 4 →  4

첫번째 비행기는 2번 게이트에 도킹하고, (2-1)번째 게이트를 차선책으로 지정한다. 
다음에 2번 게이트로 들어오는 비행기는 1번 게이트로 도킹한다는 의미다.
 

두번째 비행기도 2번 게이트로 들어오려고 한다. 위에서 언급한 2번 게이트의 차선책은 1번 게이트다.
비행기를 1번 게이트에 도킹하고, 차선책을 0번 게이트를 지정한다. 이때, 1번과 2번 게이트의 차선책은 0번이 된다.
 

세번째 비행기는 3번 게이트로 들어온다. 3번 게이트는 비어있는 상태이므로 도킹하고, 차선책으로 2번 게이트를 지정한다. 하지만 2번 게이트의 차선책은 0번 게이트다. 따라서 3번 게이트의 차선책은 0번 게이트다.
 
네번째 비행기도 3번 게이트를 들어온다. 하지만 이미 도킹이 완료된 게이트이며 차선책은 0번 게이트다. 0번 게이트는 도킹이 불가능하다. 따라서 도킹할 수 있는 최대 비행기의 수는 3개다.
 
 
<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int G = Integer.parseInt(br.readLine()); // 게이트 개수
        int P = Integer.parseInt(br.readLine()); // 비행기 개수
		
        parent = new int[G+1];
		
        // 초기화
        for (int i=1; i<=G; i++) {
            parent[i] = i;
        }
		
        int cnt = 0;
		
        for (int i=0; i<P; i++) {
            int gate = Integer.parseInt(br.readLine());
            int emptyGate = find(gate);
			
            if (emptyGate == 0) {
                break;
            }
			
            cnt++;
            union(emptyGate, emptyGate - 1);
        }
		
        System.out.println(cnt);
    }
	
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
		
        return parent[x] =  find(parent[x]);
    }
	
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
		
        if (x != y) {
            parent[x] = y;
        }
    }
}