[백준 10775번] 공항

문제 링크: 10775번 공항

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

 

먼저, i번째 비행기는 g_i에 도킹해야 하는 것이 아니라, [1, g_i]에 도킹해야 함에 주목해야 한다. 이는 곧, 들어오는 비행기마다 그리디하게, 가능한 한 오른쪽에 도킹시켜야 한다는 것을 의미한다. 그래야만 늦게 도착하는 비행기의 도킹 가능 범위가 먼저 도착한 비행기의 도킹 가능 범위보다 작더라도, 즉 g_i+k가 g_i보다 작을 때 도킹 가능한 경우가 있음에도 불구하고 도킹을 못하는 경우가 발생하지 않기 때문이다.

해결하기 어려운 문제는 여기서 발생한다. 만약에 2, 3번 게이트에 이미 비행기가 도킹되어 있다고 하고, 이 때 gi = 3인 비행기가 도착하면, 이 비행기는 1번 게이트에 도킹시켜야 한다. 그런데 이 1번이라는 위치를 찾아가기 위해서, 새로 비행기가 도착할 때마다 도킹되지 않은 게이트를 찾아 왼쪽으로 이동해가면서 탐색해나갈 수는 없는 노릇이다. 최악의 경우에 게이트가 100번까지 있을 때, 계속해서 gi = 100인 비행기만 들어온다고 생각해보면 시간복잡도가 O(n^2)이 되기 때문이다.

 

1. gi = k인 비행기가 들어오면 우리는 O(1)의 시간으로 해당 비행기가 도킹할 게이트를 찾고 싶다.

2. 탐색하는 방식은 불가능하다.

3. gi = k인 비행기가 새로 들어올 때마다, 해당 비행기가 도킹 가능한 게이트는 매번 바뀔 수 있다.

 

곧바로 떠올리기는 힘들지만, union-find를 이용할 수 있다. 처음 parent 배열은 자기 자신의 값을 가지고 있다가, 해당 게이트에 더이상 도킹할 수 없게 된다면, 해당 게이트의 왼쪽 게이트에 도킹할 수 있도록 한다. 하지만 해당 게이트의 왼쪽 게이트도 도킹할 수 없을 수 있다. 이러한 경우를 생각하여, "[해당 게이트의 왼쪽 게이트]에 도킹할 수 있도록 한다"를 "[해당 게이트의 왼쪽 게이트에 도킹을 시도했을 때 실제로 도킹하게 될 위치]에 도킹할 수 있도록 한다"로 생각을 바꾼다. 곧 parent를 따라가면 도킹 위치가 나오게 되는 것이고 이것이 find이며, 그 따라가는 과정을 줄이는 것이 union이다.

 

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

public class Main {
    static int g;
    static int p;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        g = Integer.parseInt(br.readLine());
        p = Integer.parseInt(br.readLine());
        parent = new int[g + 1]; for (int i = 0; i <= g; i++) parent[i] = i;

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

            if (cur == 0) break;
            cnt++;

            union(cur, cur - 1);
        }

        System.out.println(cnt);
    }

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

    static boolean union(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;

        parent[u] = v;

        return true;
    }
}