들어가며

완전탐색으로 생각한 풀이를 어떻게 최적화시킬 수 있는지 묻는 문제입니다. i번째 비행기를 1번부터 gi번째 게이트 중 하나에 도킹해, 비행기를 최대한 많이 도킹한다는 뜻은 gi번째 게이트에 도킹하거나 gi번째 게이트에 최대한 가까운 가능한 게이트에 도킹해야 한다는 아이디어를 떠올려야 합니다.

문제설명

1부터 G까지의 번호를 가진 게이트가 있을 때, P개의 비행기가 순서대로 도착합니다. 이 때, i번째 비행기를 1번부터 gi(1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려고 합니다. 순서대로 도착하다가 더 이상 도킹할 수 없을 때, 공항이 폐쇄됩니다. 최대 몇 대를 도킹시킬 수 있을까요?

해설

앞서 ‘들어가며’에서 설명한 것처럼 비행기를 최대한 많이 도킹하기 위해서는 gi번째 게이트에 도킹하거나 gi번째 게이트에 최대한 가까운 가능한 게이트에 도킹해야 합니다. 왜냐하면 낮은 번호의 게이트를 선점하면 이후 비행기가 도킹할 수 있는 공간이 급격히 줄어들기 때문입니다. 예를 들어, G = 4일 때, gi = 4인 비행기가 도착해 1번 게이트에 도킹해버리면, 추후 gi = 1인 비행기는 도킹할 수 없습니다. 따라서 매너있는 비행기라면 뒷 비행기를 위해 주어진 gi에 최대한 가까운 게이트에 도킹해야 하죠.

그럼 비행기가 도킹되어 있는지 확인할 수 있는 G 크기의 배열 gates를 할당하고, 각 비행기의 gi부터 낮은 번호의 게이트를 하나씩 확인하면서 비어있는 게이트를 찾아 도킹하면 풀 수 있습니다. 하지만, 한 가지 문제가 있습니다. G의 범위가 10만입니다.

예를 들어, G = 100,000이고 P = 100,000일때, 비행기가 30,000 ~ 70,000번째 게이트까지 이미 도킹되어 있다고 가정합니다. 다음 비행기들의 gi값이 70,001, 70,002, 70,003, …로 들어온다면 30,000 ~ 70,000번째 게이트를 매번 확인해야겠죠. 심지어 이 비행기들은 29,999, 29,998, 29,997, …번 게이트에 각각 도킹하므로 범위는 더 늘어날 것입니다. 즉, 70,001부터 1씩 늘어나는 gi값을 가진 비행기들이 10만까지 들어온다고 하면 40,000 + 40,001 + 40,002 + … + 70,000번의 연산을 거쳐야 합니다. 대충 최소값만 잡고 40,000 * 30,000만해도 12억입니다. 그러므로 이 비효율적인 과정을 압축해야 합니다.

그래서 첫번째 아이디어로 배열 gates 의 원소 gates[i] 를 다음과 같이 정의하겠습니다.

•

gates[i] = 1번부터 i번 중 가장 큰 비어 있는 게이트 번호

그럼 gates[i]에 접근했을 때, 가장 큰 비어 있는 게이트 번호를 바로 찾을 수 있겠죠. 값이 0이라면 1 ~ i번 게이트가 전부 차있다고 생각하면 되구요.

또 한 가지 아이디어가 있습니다. 초기 gates[i]는 전부 i입니다. 1번부터 i번 중 가장 큰 비어 있는 게이트 번호는 i 자기 자신이니까요. 따라서 i번 게이트에 비행기가 도킹되어 있다면 gates[i] ≠ i가 될 것입니다. 이를 통해 i번 게이트에 이미 비행기가 도킹되어 있는지 확인할 수 있습니다.

이 두 가지 아이디어를 통해 매번 낮은 번호의 게이트를 차례로 확인할 필요 없이 비어 있는 게이트를 곧바로 탐색할 수 있습니다. 이를 코드로 옮기면 다음과 같습니다.

코드

재귀를 이용한 풀이 (위 설명)

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        G = Integer.parseInt(br.readLine());
        gates = new int[G + 1]; // 1 ~ i번 중 도킹할 수 있는 가장 큰 게이트 번호

        for (int i = 1; i < G + 1; i++) {
            gates[i] = i; // 초기 자신의 게이트 번호로 초기화
        }

        P = Integer.parseInt(br.readLine());

        int count = 0;

        for (int i = 0; i < P; i++) {
            int gi = Integer.parseInt(br.readLine()); // gi 입력

            if (docking(gi) == -1) { // 도킹이 더이상 불가능 하다면
                break; // 중지
            } else{ // 도킹 가능하다면 count 증가
                count++;
            }

        }

        System.out.println(count);
    }

    /**
     * 도킹 과정 재귀 메서드
     */
    private static int docking(int i) {
        // 도킹 가능한 가장 큰 번호가 이미 0이라면 더이상 도킹 불가능하므로 -1 리턴
        if (gates[i] == 0) return -1;

        // 도킹 가능한 번호가 현재 i와 같다면 i번 게이트가 비어있다는 뜻
        if (gates[i] == i) {
            gates[i] = gates[i - 1]; // i - 1번 게이트의 값으로 대체해 gates[i] != i로 만들어 i번 게이트를 사용
            return gates[i];
        } else { // i번 게이트가 비어있지 않다면
            gates[i] = docking(gates[i]); // docking() 메서드를 재귀적으로 호출해 gates[i]가 가리키는 다음 게이트를 확인
            return gates[i];
        }
    }
}

gates 배열을 parent 배열로 생각하면 분리 집합, 즉 유니온-파인드로도 풀 수 있습니다.

분리집합 풀이

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        G = Integer.parseInt(br.readLine());
        gates = new int[G + 1]; // 1 ~ i번 중 도킹할 수 있는 가장 큰 게이트 번호

        for (int i = 1; i < G + 1; i++) {
            gates[i] = i; // 초기 자신의 게이트 번호로 초기화
        }

        P = Integer.parseInt(br.readLine());

        int count = 0;

        for (int i = 0; i < P; i++) {
            int gi = Integer.parseInt(br.readLine()); // gi 입력

            int possibleDockingGate = find(gi); // gi 이하에서 가능한 가장 큰 게이트 번호 찾기

            if (possibleDockingGate == 0) break; // 도킹할 게이트가 없으면 종료

            union(possibleDockingGate, possibleDockingGate - 1); // 도킹 후, 사용한 게이트를 업데이트
            count++;
        }

        System.out.println(count);
    }

    /**
     * 유니온-파인드의 파인드 메서드 (경로 압축 적용)
     */
    private static int find(int x) {
        if (gates[x] == x) return x;
        return gates[x] = find(gates[x]);
    }

    /**
     * 유니온 메서드
     */
    private static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return;

        gates[x] = y; // (x : 현재 게이트, y : 이전 게이트)로 사용할 것이므로 gates[x]에 y를 넣어야 함
    }
}

Loading comments...