[BaekJoon] 10775 공항 (Java)

1.  문제 링크

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

2.  문제

요약

• 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지 번호를 가지고 있습니다.
• 공항에는 P개의 비행기가 순서대로 도착할 예정이고, i번째 비행기를 1번부터 $g_i$번째 게이트 중 하나에 영구적으로 도킹하려고 합니다.
• 비행기가 어느 게이트에도 도킹할 수 없다면 공ㅎ앙이 폐쇄되고 이후 어떤 비행기도 도착할 수 없습니다.
• 비행기에 대한 정보가 주어질 때, 도킹시킬 수 있는 최대 비행기 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 $10^5$보다 작거나 같은 게이트의 수 G가 주어지고 두 번째 줄에는 1보다 크거나 같고 $10^5$보다 작거나 같은 비행기의 수 P가 주어지며 세 번째 줄부터 P개의 줄에 1보다 크거나 같고 G보다 작거나 같은 $g_i$가 주어집니다.
• 출력: 첫 번째 줄에 도킹시킬 수 있는 최대 비행기 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int G, P;
    static int[] gates, parents;

    static void input() {
        Reader scanner = new Reader();
        G = scanner.nextInt();
        P = scanner.nextInt();
        gates = new int[P];

        for(int idx = 0; idx < P; idx++)
            gates[idx] = scanner.nextInt();
    }

    static void solution() {
        init(G + 1);

        int answer = 0;
        
        for(int idx = 0; idx < P; idx++) {
            int gate = findParent(gates[idx]);

            if(gate == 0) break;

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

        System.out.println(answer);
    }

    static void init(int size) {
        parents = new int[size];

        for(int gate = 0; gate < size; gate++)
            parents[gate] = gate;
    }

    static int findParent(int gate) {
        if(gate == parents[gate]) return gate;
        return parents[gate] = findParent(parents[gate]);
    }

    static void union(int gate1, int gate2) {
        int parent1 = findParent(gate1), parent2 = findParent(gate2);

        if(parent1 != parent2) {
            if(parent1 < parent2) parents[parent2] = parent1;
            else parents[parent1] = parent2;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}