공항

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

풀이

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

생일 선물로 공항을 사주는 친구 어디 없나...

공항의 게이트에 비행기를 도킹하는데 만약 도킹할 수 있는 게이트가 없다면 공항은 폐쇄된다.

모든 게이트에 대해 boolean 배열을 만들어 비행기가 도킹하면 해당 인덱스를 true로 만드는 것을 통해 문제를 풀 수 있다. 하지만 입력값이 크기때문에 n^2의 방법으로는 시간 초과에 직면한다.

문제의 분류에 분리 집합. 즉, 유니온-파인드 알고리즘을 사용하면 시간내에 풀 수 있다.

비행기가 특정 게이트에 도킹이 성공했다면 다음 같은 번호 비행기는 성공한 게이트보다 1작은 번호의 게이트에 도킹할 수 있다. 즉 1작은 번호의 게이트와 도킹에 성공한 게이트를 하나의 집합으로 묶으면 비행기가 다음 도킹해야할 위치를 지정해 줄 수 있다.

게이트 번호가 1부터 시작하기때문에 find(num)을 통해 구한 값이 0보다 크다면 유니온을 통해 집합으로 묶어 주고 만약 find(num)의 값이 0이라면 모든 게이트가 꽉찬 것이기 때문에 공항이 폐쇄되고 종료하면 된다.

코드

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

public class Main {
    static int n, m, k;
    static int[] rank;
    static int[] pa;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int p = Integer.parseInt(br.readLine());

        pa = new int[n + 1];
        rank = new int[n + 1];

        for (int i = 0; i <= n; i++)
            pa[i] = i;

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

            if(k > 0) {
                union(k - 1, num);
                cnt++;
            }
            if(k == 0)
                break;
        }
        bw.write(cnt + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot != bRoot) {
            if (aRoot == pa[aRoot])
                pa[bRoot] = aRoot;
            else
                pa[aRoot] = bRoot;
        }
    }

    static int find(int a) {
        if (pa[a] < 0 || pa[a] == a) {
            return a;
        } else {
            int y = find(pa[a]);
            pa[a] = y;
            return y;
        }
    }
}