백준 10775번 - 공항

문제

백준 10775번 - 공항

아이디어

• 비행기가 도킹할 수 있는 게이트는 제한되어 있다.
• 1번 비행기는 1번 게이트만, 2번 게이트는 1~2번 게이트만, 3번 게이트는 1~3번 게이트만 된다.
• 그리고 각 게이트는 하나의 비행기만 도킹될 수 있다.
• 가장 많이 도킹이 되려면 해당 게이트가 이미 도킹되어 사용하지 못할 때 이전 게이트라도 도킹이 되어야 한다.
• 예를 들어 4개의 게이트가 있고, 4개의 비행기가 4, 4, 4, 4순서로 왔을 때 처음 비행기는 4번에 도킹한다. 두번째 비행기는 4번에 도킹할 수 없으므로 3번에 도킹할 수 없다. 세번째 비행기는 2번, 마지막 비행기는 1번에 도킹하도록 할 수 있다.
• 이는 유니온-파인드로 구현할 수 있다.

예상 시간 복잡도

• 비행기, 게이트의 수 : n
• 예상 시간 복잡도 : O(n)

코드 구현

package Baekjoon.greedy;

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

/**
 * <a href = "https://www.acmicpc.net/problem/10775">백준 10775번 - 그리디 : 공항</a>
 * <br>
 * <a href = "">velog</a>
 * @since 2024-07-30
 */
public class BJ_10775 {

    static int[] parent;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int gate = Integer.parseInt(br.readLine());
        int p = Integer.parseInt(br.readLine());

        parent = new int[gate + 1];
        for (int i = 1; i <= gate; i++) {
            parent[i] = i;
        }

        int count = 0;

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

            int temp = find(g); //도킹 가능한 게이트 찾기

            if (temp == 0) { //도킹 불가능
                break;
            }

            count++;

            union(temp - 1, temp); //이전 게이트로 업데이트
        }

        System.out.println(count);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

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