백준 10775번: 공항 (Java)

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

10775번: 공항

 

 

 

 

 

 

 

 

---

딱 보고 '이분 매칭'아니야? 라고 생각을 해서 알고리즘 태그를 까서 봤습니다. 스포당해서 제대로 푼 느낌이 아니네요. 스케줄링 유형의 문제에 약합니다.

 

풀이

도착한 사람이 현재 갈 수 있는 게이트 중 가장 큰 숫자로 배치시켜야 합니다. 그러려면, 현재 나온 숫자에서 거슬러 올라가면서 아직 사용하지 않은 게이트 중 가장 큰 숫자를 찾으면 됩니다.

가장 먼저 생각나는 구현 방법으로는, 적당한 boolean 배열을 만들어 !visited[$i$]일 때까지 거슬러 올라가다가, !visited[$i$]인 $i$를 찾으면 도킹시키고, 만약 $ i = 0 $이면 도킹할 수 있는 게이트가 없다는 뜻이니 중단시키는 방법일 겁니다. 다만, 이 알고리즘은 시간 복잡도가 $O(P^2)$라, $ G = 10^5, P = 10^5, G_i = 10^5$ 
인 경우 최대 $ 10^{10} $ 번 '언저리'의 연산을 수행하여 시간 초과가 발생합니다.

따라서, 유니온 파인드를 사용하여, (현재 게이트보다 작은 게이트 중 도킹되지 않은 가장 큰 게이트)를 현재 게이트의 조상으로 가지도록 합니다. 아이디어가 참신합니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] p;
    
    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());
        makeSet(G);
        int cnt = 0;
        for (int i = 0; i < P; i++) {
            int cur = Integer.parseInt(br.readLine());
            int loc = findRoot(cur);
            if (loc == 0) break;
            union(loc-1, loc);
            cnt++;
        }
        System.out.println(cnt);
    }
    
    static void makeSet(int N) {
        p = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            p[i] = i;
        }
    }
 
    static int findRoot(int a) {
        if (a == p[a])
            return a;
        return p[a] = findRoot(p[a]);
    }
 
    static boolean union(int a, int b) {
        a = findRoot(a);
        b = findRoot(b);
        if (a == b) return false;
        p[b] = a;
        return true;
    }
}