백준 10775: 공항 [Java] - 포포

문제

 

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

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

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

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

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

입력

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

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

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

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다. 
https://www.acmicpc.net/problem/10775

---

도킹시킬 수 있는 최대의 비행기 수를 출력하려면,
각각의 비행기가 도킹할 수 있는 게이트 번호가 최대가 되어야 한다.
예를들어, 

예제 입력 1

4 3 4 1 1

위와 같은 입력을 받는다면,
게이트는 총 4개, 비행기는 총 3대이며
첫번째 비행기는 4번 게이트, 두번째 비행기는 1번 게이트, 마지막 세번째 비행기는 1번 게이트만 도킹이 가능하나
이미 사용중이므로 도킹이 불가능 해 2를 출력해야 한다.

아무튼, 각각의 비행기가 도킹할 때 가능한 범위내에서 가장 큰 게이트 번호에서 도킹이 이루어져야 한다.

맨 처음 구현한 코드에서는 
각각의 비행기를 배열에 집어넣고, 해당 배열이 사용중이면(해당 게이트가 이미 도킹되었으면) 배열의 인덱스를 1씩 줄여가며 빈 공간을 찾는 코드였다. 인덱스가 0이 되면 도킹했던 비행기의 수를 출력하고 코드를 종료했다.  

시간복잡도가 O(N^2)이었는데 , 예상대로 예제 입력의 최대값이 10^5라 시간초과가 발생했다. 
도무지 O(N)의 복잡도로 해결할 방법이 떠오르지 않아 검색을 해보았는데 
모든 블로그가 풀이로 유니온 파인드(합집합 찾기)를 소개했다.
그래서 나도 간단히 정리했다.
2022.05.24 - [알고리즘] - Union find(합집합 찾기, 서로소 집합) 알고리즘

유니온 파인드에 대해서는 아래 문제를 해결하면서 내일 자세히 다룰 계획이다.
https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

---

제출한 코드

package com.company.greedy;

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

public class No10775 {
    static int[] parent;
    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());
        parent = new int[G + 1];
        for (int i = 1; i <= G; i++) {
            parent[i] = i;     //처음에 각 노드는 자기 자신이 부모인 상태(각 노드가 독립적임. 연결X)
        }
        int ans = 0;
        for (int i=0;i<P;i++) {
            int g = Integer.parseInt(br.readLine());
            int emptyGate = find(g); //부모 노드를 찾는다
            if (emptyGate != 0) {  //게이트에 도킹이 가능한 경우
                ans++;
                union(emptyGate, emptyGate - 1);  // emptyGate와 emptyGate -1 노드의 부모를 합친다.
            } else {
                break;
            }
        }
        System.out.println(ans);
    }

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

    static void union(int x, int y) {
    	//x, y의 부모 값을 구한 뒤 더 작은 값으로 부모를 합친다.
        x = find(x);
        y = find(y);

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