[백준] 10775번 공항 JAVA

문제

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

10775번: 공항

 

---

풀이 방법

 

문제 유형 : 그리디 & 유니온 파인드

 

 

그리디 접근

각각 gi에 따라 도킹할 수 있는 게이트는 다음과 같다.

1번 게이트는 1,2,3,4인 비행기가 도킹할 수 있고,

2번 게이트는 2,3,4인 비행기가 도킹할 수 있고,

...,

4번 게이트는 4인 비행기만 도킹할 수 있다.

-> 4인 비행기가 자기만 사용할 수 있는 게이트를 사용하는 게 가장 좋지 않을 까?

 

 

N인 비행기는 N번 게이트가 비어있다면 N번 게이트에 도킹한다.

N번 게이트가 비어있지 않다면 N-1번 게이트가 비어있는지 확인하고 도킹한다.

....

1번 게이트가 비어있는지 확인하고 도킹한다.

1번 게이트가 비어있지 않다면 도킹을 할 수 없다.

 

 

순차 탐색으로 접근

N인 비행기가 N번 들어온다면,

1번 째 N인 비행기 -> N번 게이트에 도킹 O(1)

2번 째 N인 비행기 -> N-1번 게이트에 도킹 O(2)

3번 째 N인 비행기 -> N-1번 게이트에 도킹 O(3)

4번 째 N인 비행기 -> N-1번 게이트에 도킹 O(4)

...

비행기가 P번 들어온다면 시간 복잡도는 O(P^2)

 

따라서 N인 비행기가 어디에 도킹을 해야할 지 빠르게 찾을 수 있는 방법이 필요

 

 

 

유니온 파인드

각 게이트를 유니온 파인드 자료구조로 표현한다.

 

 

5번 게이트를 사용했다면, 4번 게이트의 자식으로 연결한다.

(사용한 게이트)를 자식으로 하고 (사용한 게이트 번호 -1)을 부모로 연결하면

find(5)를 통해 다음에 들어갈 게이트를 바로 찾을 수 있다.

 

 

 

테케 2번 예시

 

초기 상태

 

 

 

find(2)의 결과인 2번 게이트가 비어있으므로 2를 1과 연결한다.

 

 

 

 

find(2)의 결과인 1번 게이트가 비어있으므로 1을 0과 연결한다.

 

 

find(3)의 결과인 3번 게이트가 비어있으므로 3을 2와 연결한다.

find(3)의 결과인 3번 게이트가 비어있지 않으므로 종료한다.

---

코드 

public class BOJ_10775_공항 {
	
	static int[] u;
	static int find(int a) {
		if(u[a] < 0)return a;
		return u[a] = find(u[a]);
	}
	static void merge(int a,int b) {
		a = find(a);
		b = find(b);
		if(a==b)return;
		u[a] += u[b];
		u[b] = a;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int G = Integer.parseInt(in.readLine());
		int P = Integer.parseInt(in.readLine());
		
		u = new int[G+1];
		Arrays.fill(u, -1);
		
		int cnt = 0;
		for(cnt =0;cnt <P;cnt++) {
			int airplane = Integer.parseInt(in.readLine());
			int blankGate = find(airplane);
			if(blankGate == 0) {
				break;
			}
			
			merge(blankGate-1, blankGate);
		}
		
		System.out.println(cnt);
	}
}