[백준 10775] 공항 -JAVA

문제

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

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

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

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

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다.

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

입력

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

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

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

출력

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

---

접근 방법

비행기가 한대씩 오고 $i$번째 비행기를 1번부터 $g_i$번 게이트 중 하나에 도킹해야하는데
우선 가장 많은 비행기를 도킹 시키려면
도킹 범위 내에서 아직 도킹되지 않은 게이트 중 가장 높은 번호의 게이트를 선택하면 됩니다.

다른 예외 케이스는 없고 그리디하게 문제를 해결하면 되는 문제입니다.
다만 게이트 수와 비행기 수의 최대가 $10^5$으로
문제를 $O(PlogG)$ 이내에 찾아야 한다는 것입니다.

$O(PlogG)$인 이유는
입력으로 $P$개 주어지는데 이 입력에 대해 선형 시간으로 해결해야 하며
하나의 비행기가 게이트를 찾는데 $O(logG)$이내의 시간이 걸려야 해결할 수 있는 문제입니다.

그래서 생각한 방법은 두 가지 방법 입니다.

• 게이트 배열 선언 후 범위 내의 도킹 가능한 위치를 이분 탐색으로 $O(PlogG)$시간 내에 찾기
• 유니온 파인드(분리 집합)로 현재 범위 내에서 도킹 가능한 위치를 parent 배열로 저장하고 find

첫 번째 방법은 아무 위치나 삽입한다는 전제라면 가능하겠지만
그리디하게 풀기 위해
도킹 범위 내에서 아직 도킹되지 않은 게이트 중
가장 높은 번호의 게이트를 찾아야 하기 때문에
두 번째 방법으로 풀게 되어 $O(P \alpha(G))$의 시간 복잡도로 문제를 풀 수 있었습니다.

유니온 파인드 구현 방식은 다음과 같습니다.

• Find의 역할 (가장 큰 빈 게이트 찾기)
  • 비행기가 $g_i$ 게이트를 요청하면, $find(g_i)$를 실행합니다.
  • Find는 $g_i$ 이하에서 현재 도킹 가능한 게이트 중 가장 큰 번호 $b$를 찾아줍니다.
  • 경로 압축을 통해 한 번 찾았던 경로는 다음번에 바로 루트(빈 게이트)로 연결되어, 검색 속도가 극도로 빠릅니다.
• Union의 역할 (도킹 후 '다음' 게이트로 연결)
  • 비행기가 게이트 $b$에 도킹하면, $b$는 이제 사용 중입니다.
  • Union 연산은 게이트 $b$의 부모를 $b-1$ 게이트의 루트로 설정합니다.
  • 의미: 다음에 $b$를 찾는 비행기는 자동으로 $b-1$ 이하에서 사용 가능한 게이트를 안내받게 됩니다.

---

코드

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


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

        parent = new int[G+1];

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

        int count = 0;
        while (count < P) {
            int airplane = Integer.parseInt(br.readLine());
            if (!union(airplane)) break;
            count++;
        }

        System.out.println(count);
    }


    private static boolean union(int a) {
        int b = find(a);

        if (b == 0) return false;

        parent[b] = find(b-1);

        return true;
    }

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