백준 공항 10775

백준 공항 10775 바로가기

문제 설명

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

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

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

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

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

접근 방식

그리디와 유니온 파인드를 사용하였다.

우선 그리디한 접근으로는 gi 번의 비행기가 들어오면

i, i - 1, … 2, 1번 공항 순으로 탐색하다가 빈 공항이 있으면 도킹을 하는것이다.

유니온 파인드는,

쉽게 설명하자면 4번 공항이 도킹 되었을 때, 또 4번 공항으로 비행기가 들어오면 3번으로 가라고 알려줘야하는것이다.

즉 도킹이 끝나면 전의 공항을 가리키게 바꿔주면 되는것이다.

여기서 유니온 파인드가 쓰인다.

코드

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

public class Main {
    static int[] parents;

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

        int answer = 0;

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

        parents = new int[G + 1];
        for (int i = 0; i <= G; i++) {
            parents[i] = i;
        }

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

        for (int plane : myList) {
            int k = findRoot(plane);
            if (k == 0) break;
            else {
                union(k - 1, k);
                answer++;
            }
        }
        System.out.println(answer);

    }

    private static int findRoot(int x) {
        if (parents[x] == x) return x;
        else return parents[x] = findRoot(parents[x]);
    }

    private static void union(int a, int b) {
        parents[b] = findRoot(a);
    }

}

Disscussion

그리디한 접근까지는 다소 쉬웠으나 유니온 파인드 접근이 많이 어려웠다.

더 많이 문제를 풀어보자!!