bj10775 공항(유니온 파인드, 그리디)

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

1~g번까지의 포트에 도킹을 할 수 있다.

정렬을 사용하지 못한다.

즉, g가 클 수록 번호가 큰 포트를 이용해야 최대의 값을 구할 수 있다.

 

이중 for문으로 1~P까지의 비행기를 채워지지 않은 가장 뒤의 포트를 찾고 도킹하는 방식으로 구현해보았더니,

시간 초과가 났다.

 

즉, 가장 뒤의 포트를 찾는 로직에서 시간 복잡도를 줄여야한다.

1,2,3,4,5,6,7 포트가 남아있을때, 3번에만 도킹할 수 있는 비행기가 있다면

1,2,2,4,5,6,7 이런 방식으로 유니온 파인드를 이용해, 어디에 넣을 수 있는지 찾을 수 있다.

1,1,1,4,5,6,7 => 2번에만 도킹할 수 있는 비행기

 

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

public class Main {
    static int[] parent;
    static int G, P;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        
        G = Integer.parseInt(bufferedReader.readLine());
        P = Integer.parseInt(bufferedReader.readLine());

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

        int ans = 0;
        for (int i = 0; i < P; i++) {
            int gate = Integer.parseInt(bufferedReader.readLine());

            int availableGate = find(gate);
            if (availableGate == 0) {
                break;
            }
            
            union(availableGate, availableGate - 1);
            ans++;
        }

        System.out.println(ans);
    }

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

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