[JAVA]백준 10775번: 공항

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

10775번: 공항

1. 문제 설명

 

문제

• 공항에는 G게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
• 공항에는 P개의 비행기가 순서대로 도착한다.
• i번째 비행기를 1번부터 gi번째 게이트 중 하나에 영구적으로 도킹할 수 있다.
• 최대 몇 개를 도킹시킬 수 있는지 구하는 문제

조건

• 1<=게이트의 수, 비행기의 수 <=10^5

 

2. 풀이

 

유니온 파인드 알고리즘으로 풀 수 있다.

 

최대한 많은 비행기를 도킹시키기 위해서는 비행기 gi가 도착했을 때, gi부터 순서대로 채워나가는 것이다.

 

따라서, 유니온 파인드 알고리즘을 통해, 현재 어느 칸에 비행기를 도킹시킬 수 있는지 확인하는 것이다.

 

현재 비행기 gi의 부모를 확인하고 0이면 도킹할 자리가 없는 것이므로 반복 종료.

 

0이 아니라면 현재 칸을 비행기에 도킹한 것을 표시하기 위해, 자신의 부모와 자신의 부모 -1을 union 한다.

 

자신의 부모가 가리키는 것은 현재 gi가 도킹할 수 있는 칸의 개수이고, gi를 도킹함으로 한자리를 사용했기에 자신의 부모 -1을 하여 union 하는 것이다.

 

처음에는 간단한 누적합 문제라고 생각하고 세그먼트 트리를 통해 풀려고 시도했다.

 

비행기 gi가 도착했을 때 1부터 gi까지의 누적합을 계산하고, 누적합이 gi 미만이라면 도킹 횟수를 증가시켰다.

 

간과한 것은 gi보다 큰 비행기들이 이미 많이 도착해있어서 빈자리가 없을 수 있다는 것이다.

 

예를 들어, 게이트의 수가 4이고 비행기의 수가 4라고 해보자.

 

그리고 2 2 1 1 순서로 비행기가 들어온다고 가정하자.

 

3번째 1 비행기가 들어왔을 때, 1 비행기가 들어갈 자리는 없지만, 1부터 1까지의 누적합은 0이기 때문에 도킹 횟수를 증가시키기 된다.

 

이러한 예외 처리를 해주어 세그먼트 트리로 풀 수도 있지만, 유니온 파인드로 푸는 게 간단하여 굳이 구현하지는 않았다.

 

 

 

*로직

1. gi의 부모를 구한다.

2. 0일 경우 반복 종료

3. gi, gi-1 union

 

3. 코드

// JAVA 11 , 메모리 : 22668KB, 시간 : 252ms

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

public class Main {

    public static int[] parent;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int gateNum, planeNum;
        int now, nowParent, answer;

        gateNum = Integer.parseInt(br.readLine());
        planeNum = Integer.parseInt(br.readLine());

        parent = new int[gateNum + 1];

        answer = planeNum;

        for (int x = 0; x <= gateNum; x++) {
            parent[x] = x;
        }

        for (int x = 0; x < planeNum; x++) {
            now = Integer.parseInt(br.readLine());

            nowParent = find(now);

            // 빈공간이 없으면 끝
            if (nowParent == 0) {
                answer = x;
                break;
            }

            union(nowParent, nowParent - 1);
        }

        bw.write(String.valueOf(answer));
        bw.flush();



    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            parent[x] = y;
        }
    }

    // 몇개의 공간이 비어있는지 체크
    public static int find(int x) {
        if(parent[x]==x)
            return x;
        else
            return parent[x] = find(parent[x]);
    }




}