[백준, Java] 10775번 : 공항

🔗 문제 링크

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

😮 문제 해결 방법

문제에서 비행기가 순서대로 도착할 예정이고 각 비행기의 값은 1부터 해당 값까지의 게이트에 도킹할 수 있는 것을 의미한다.

자신의 순서에 비행기가 도킹할 수 없을 때까지 개수를 세준다.

비행기가 도킹할 수 있는 게이트를 찾기 위해서 Union-Find를 이용한다.

 

게이트 배열을 자신의 게이트로 초기화를 하고, 해당 값의 비행기가 도킹되면 다음에 도킹될 동일한 값의 비행기는 현재 게이트보다 하나 작은 게이트로 도킹되어야 한다.

 

예를 들어, 게이트가 4개이고 아무 비행기도 게이트에 도킹되지 않았다면 게이트 배열은 1,2,3,4값을 가질 것이다.

3번 비행기가 3번 게이트에 도킹되면 이 후에 들어오는 3번 비행기는 1 아니면 2번 게이트에 도킹되어야 한다. 2번 게이트로 들어올 때 도킹될 수 있는 게이트와 3번 게이트로 들어올 때 도킹될 수 있는 게이트를 합쳐준다.

 

이 때, Union - Find를 이용해 다음 도킹될 게이트를 집합으로 합쳐준다

1. 현재 이용 가능한 가장 큰 게이트를 find 연산을 통해 찾는다.
2. 만약 찾은 게이트가 0번 게이트라면 (도킹할 수 없는 경우) 반복문을 탈출한다 .
3. 현재 이용 가능한 가장 큰 게이트를 이용했다면, 현재 이용한 게이트와 다음번에 동일한 값을 가진 비행기가 도킹할 게이트 (현재 이용한 게이트 -1)과 Union연산을 통해 다음 도킹할 게이트를 만들어준다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main_10775_공항 {
    private static List<Integer> plane;
    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());

        plane = new ArrayList<>();
        for (int airplane = 0; airplane < P; airplane++) {
            plane.add(Integer.parseInt(br.readLine()));
        }

        int rst = dockingAirplane(G, P);
        System.out.println(rst);
        br.close();
    }

    private static int dockingAirplane(int g, int p) {
        int[] gates = new int[g + 1];
        for (int gate = 1; gate <= g; gate++) {
            gates[gate] = gate;
        }

        int count = 0;
        for (Integer airplane : plane) {
            // 이용가능한 게이트 찾기
            int availableGate = find(gates, airplane);
						// 이용 가능한 게이트가 없다면 반복문 탈출
            if(availableGate < 1) break;

            // 게이트에 배치 했으니 현재 비행기와 동일한 게이트 번호를 가진 비행기 도킹 시 현재 게이트보다 하나 작은 게이트를 이용 필요
            union(airplane, availableGate - 1, gates);

            count++;
        }

        return count;
    }

    private static void union(Integer airplane, int nextAvailable, int[] gates) {
        int curGate = find(gates, airplane);    // 현재 비행기가 이용중인 게이트 찾기
        int nextGate = find(gates, nextAvailable);  // 동일한 게이트 번호 비행기가 다음에 도킹시 사용할 게이트 찾기

        if(curGate > nextGate) gates[curGate] = nextGate;
        else gates[nextGate] = curGate;
    }

    private static int find(int[] gates, Integer airplane) {
        if(gates[airplane] != airplane) gates[airplane] = find(gates, gates[airplane]);
        return gates[airplane];
    }
}