[ BOJ ][JAVA][10775] 공항

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

10775번: 공항

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	8039	3016	2180	37.933%

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

예제 입력 1

4
3
4
1
1

예제 출력 1

2

예제 입력 2

4
6
2
2
3
3
4
4

예제 출력 2

3

코드

/*
    공항
    union-find + greedy

    g번 게이트는 g번 이하의 게이트에만 도킹할 수 있다.
    만약 g번이 비어있다면 해당 게이트에 도킹하는 것이 최선이다.
    g번 게이트를 도킹할 수 없다면 g-1 게이트를 도킹하는 것이 최선.
    ... 0번까지 탐색 하여, 차선책이 0번을 가리킨다면 도킹 불가능 상태로 종료
*/
import java.io.*;
import java.util.*;
public class p10775 {
    static int g, p;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        g = Integer.parseInt(br.readLine());
        p = Integer.parseInt(br.readLine());

        parent = new int[g + 1];
        for (int i = 0; i <= g; i++) {
            parent[i] = i;
        }

        int answer = 0;
        for (int i = 0; i < p; i++) {
            int num = Integer.parseInt(br.readLine());
            int empty = find(num);

            if (empty == 0) break;

            answer++;
            // 차선책을 계속해서 연결해준다.
            union(empty, empty - 1);
        }
        System.out.println(answer);
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            parent[u] = v;
        }
    }

    static int find(int x) {
        if (x == parent[x]) return x;

        return parent[x] = find(parent[x]);
    }
}