백준 10775 공항 java

문제 소개 www.acmicpc.net/problem/10775

내용

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

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

비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

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

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

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

출력

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

해결 방법

아이디어

그리디 알고리즘과 유니온파인드 알고리즘으로 해결가능하다.

gi에서 최선책은 gi의 값이 된다. gi에 도킹했다면 gi -1 이 차선책이 된다. 

이렇게 도킹할때마다 해당 값의 차선책을 연결해주면 해결할 수 있다.

실제 풀이 코드

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int gatewayCount = Integer.parseInt(br.readLine());
        int plainCount = Integer.parseInt(br.readLine());

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

        int answer = 0;
        for (int i = 0; i < plainCount; i++) {
            int g = Integer.parseInt(br.readLine());
            int emptyGate = getParents(g);

            if (emptyGate == 0) {
                break;
            }

            answer++;
            union(emptyGate, emptyGate - 1);
        }

        System.out.println(answer);
    }

    public static int getParents(int x) {
        if (x == parent[x]) return x;
        return parent[x] = getParents(parent[x]);
    }

    public static void union(int x, int y) {
        x = getParents(x);
        y = getParents(y);

        if (x != y) {
            parent[x] = y;
        }
    }
}

결과