[백준 P10775] 공항 Java

P10775 공항

10775번: 공항

문제

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

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

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

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

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력값

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 100,000)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 100,000)가 주어진다.

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

4
3
4
1
1

4
6
2
2
3
3
4
4

출력값

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

2

3

알고리즘

이 문제는 아이디어를 떠올리는게 어려웠다. 우선 문제를 잘 살펴보자.

공항은 G개의 게이트가 있고 각 게이트는 1부터 G까지 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착한다. 각 비행기도 번호를 가지고 있는데, 번호보다 작거나 같은 게이트에만 도킹을 할 수 있다. 비행기가 어느 게이트에 도킹할 수 없다면 공항이 폐쇄된다.

4개의 게이트가 있을 때, [2, 2, 2] 순서대로 비행기가 들어온다고 가정해보자.

첫 번째 2번 비행기는 2번 게이트에 도킹하면 된다. 그 다음 들어오는 2번 비행기는 2번에 이미 비행기가 도킹되어 있으므로 1번 게이트에 도킹한다. 이후에 들어오는 3번째 비행기의 경우에는 2번이 이미 도킹되어 있고, 1번도 도킹되어 있으므로 더 이상 도킹할 수 없다. 이 경우에 공항은 폐쇄되고 승원이는 총 2개의 비행기를 도킹하게 된다.

이를 그림으로 보면 다음과 같다. 배열의 인덱스는 게이트, 값은 해당 게이트보다 작은 게이트 중 도킹을 시도할 수 있는 게이트를 저장한다.

우선 처음에는 모든 게이트가 열려있고 3대의 비행기가 2번 게이트에 도킹을 시도하고 있다. 처음으로 도착한 비행기는 2번 게이트가 열려있기 때문에 2번에 도킹한다.

 

그 다음 비행기가 2번으로 도킹을 시도한다. 현재 게이트 2의 값이 1이기 때문에 2번 게이트는 도킹을 시도할 수 없고 1번으로 도킹을 시도한다. 1번 게이트는 비어있기 때문에 1번 게이트에 도킹한다. 1번 게이트의 값이 1보다 하나 작은 0으로 바뀐다.

마지막으로 2번 비행기가 도킹을 시도한다. 2번 게이트를 보니 현재 1으로 기록되어 있으므로 1번 게이트의 값을 얻어서 본인의 값과 바꾼다. (최적화 하기 위함이다.) 그 다음 1번 게이트가 0을 가리키고 있으므로 1번 게이트에 도킹이 불가능하다는 것을 알게 된다. 1번이 가장 작은 숫자의 게이트 이므로 더 이상 도킹할 게이트는 없다고 판단하며 실행을 종료한다.

이를 코드로 구현하기 위해서 Union-Find를 사용했다.

들어오는 비행기의 번호를 보고 그 번호의 게이트에 도킹할 수 없다면 그 번호의 -1 번째 게이트의 대표값으로 값을 수정하고 도킹을 시도한다. 도킹이 가능할 때 까지 탐색하고 union 시켜준다. 만약 도킹이 불가능하다면 실행을 종료한다. 코드는 다음과 같다.

코드

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

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

    public static void main(String[] args) throws Exception {
        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 = 1; i <= G; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < P; i++) {
            int gate = find(Integer.parseInt(br.readLine()));
            if (find(gate) != 0) {
                union(gate, gate - 1);
                answer++;
            } else {
                break;
            }
        }

        System.out.println(answer);
    }

    public static void union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);

        if (aParent < bParent) {
            parent[bParent] = aParent;
        } else {
            parent[aParent] = bParent;
        }
    }

    public static int find(int target) {
        if (parent[target] == target) {
            return target;
        } else {
            return parent[target] = find(parent[target]);
        }
    }
}