[BaekJoon] 10775 공항 (Java)

🔗 문제 링크

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

📝 문제 설명

해당 문제는 Greedy로 각 비행기에 주어진 gi값보다 작은 수 중에서 비어있는 게이트에 비행기를 연결시키면 되는 간단한 문제이다.

하지만 일반적인 Greedy방식으로 문제를 풀게 된다면 문제에 주어진 시간제한이 짧아 시간초과라는 결과를 받게 된다.

그래서 문제를 통과시키기 위해서는 아래의 작성한 코드와 같이 Union-find 코드를 작성하여 각각의 parent를 통해 비어있는 위치를 찾아 연산의 시간을 줄여야합니다.

👨🏻‍💻 작성한 코드

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

public class Main {

	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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=0; i<=G; i++) parent[i] = i;
		
		int count = 0;
		for (int i=0; i<P; i++) {
			int g = Integer.parseInt(br.readLine());
			int parentGate = find(g);
			if (parentGate != 0) {
				count++;
				union(parentGate-1, parentGate);
			}
			else break;
		}
		System.out.println(count);
	}
	
	static int find(int g) {
		if (parent[g] == g) return g;
		return parent[g] = find(parent[g]);
	}
	
	static void union(int g1, int g2) {
		int p1 = find(g1);
		int p2 = find(g2);
		
		if (p1 < p2) parent[p2] = p1;
		else parent[p1] = p2;
	}
}