[BOJ] 백준 10775번 공항 (Java)

#10775 공항

난이도 : 골드 2

유형 : 그리디 / Union-Find

10775번: 공항

▸ 문제

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

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

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

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

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

▸ 입력

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

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

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

▸ 출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

문제 풀이  

가장 끝 번호를 가지는 게이트부터 도킹을 하는 단순 그리디 문제인 줄 알았지만 그냥 풀이를 하면 시간초과가 발생한다. 백준 9576번 책 나눠주기 문제랑 같은 그리디 방식이고 추가로 효율성 과제까지 주어졌는데 난이도는 왜 더 낮은지 모르겠다.

 

끝 번호부터 도킹을 하는 이유는 다음과 같다. 만약 도착하는 순서대로 끝이 아닌 중간 혹은 첫 번호부터 도킹을 한다면 어떻게 될까? 만약 2 1로 도착한다면 뒤에 오는 비행기는 도킹을 하지 못한다. 따라서 끝 번호부터 도킹을 함으로써 먼저 도착하는 비행기를 최대한 마지막 번호(g)에  도킹시킴으로써 뒤에 올 비행기들에게 도킹할 수 있는 최대한 많은 범위(1~g-1)를 주어질 수 있다.

 

그러나, 여기까지 구현하면 시간초과가 발생한다. 왜냐하면 10^5개의 비행기들이 매번 자신이 도킹해야하는 공항을 (1+2+...+10^5)를 탐색하게 된다면 O(N^2)으로 10^10으로 시간초과가 발생하기 때문이다. 연산 줄일 방법이 생각이 안나 질문 글을 참고하여 Union-Find라는 힌트를 얻었다.

 

Union-Find를 사용하면 G게이트를 목적으로 도착하는 모든 비행기들에게 Parents[G]를 O(1)로 전송함으로써 도킹할 수 있는 게이트를 바로 전달할 수 있기 때문이다. 이 테크닉을 경로 압축(Path Compression)이라고 부른다고 한다. 오늘도 하나 배웠다!

 

시뮬레이션

예제로 시뮬레이션을 돌려보면 다음과 같다.  총 게이트의 수는 4개이고, 비행기 도착 순서는 2 2 3 3 4 4 이다.

 

초기 상태는 다음과 같다.

초기 상태

 

1. 첫 번째 비행기 도착. 1~G에서 가능한 가장 끝 번호 게이트를 선택한다. parents[2] = 2이므로 2에 도킹시킨 후다음 비행기가 만약 G(2)로 도착한다면 바로 parents[2] = 1로 이동시키도록 설정한다.

 

첫 번째 비행기 도착. G=2

 

2. 두 번째 비행기 도착. 1~G에서 가능한 가장 끝 번호 게이트(2)를 선택한다. parents[2] = 1이므로 1에 도킹시킨 후 다음에 도착하는 비행기는 parents[2 > 1] = 0로 이동시키도록 설정한다.

 

두 번째 비행기 도착. G=2

 

3. 세 번째 비행기 도착. 1~G에서 가능한 가장 끝 번호 게이트(3)를 선택한다. 그리고 다음 비행기가 만약 G(3)로 도착한다면 바로 parents[3 > 2 > 1] = 0 로 이동시키도록 설정한다.

 

세 번째 비행기 도착. G=3

 

4. 네 번째 비행기 도착. 1~G에서 가능한 가장 끝 번호 게이트(3)를 선택한다. 그런데 parents[3] = 0 이므로, 더이상 도킹할 게이트가 없으므로 공항을 폐쇄시킨다.

네 번째 비행기 도착. G=3

 

따라서, 도킹할 수 있는 최대의 비행기 수는 3이다.

 

설계

1. 비행기를 도착하는 순대로 차례대로 도킹시킨다 for i : 0~p
2. 도착하는 비행기의 G의 부모 게이트를 찾아 도킹시킨다.
   1. 만약 부모 게이트가 0이라면 도킹할 게이트가 없으므로 공항을 폐쇄시킨다. if(find(l) ==0) break;
   2. 도킹을 한 후 해당 노드의 (부모 게이트-1)을 연결시킨다. union(find(l), find(l)-1);
3. 도킹한 비행기의 수를 출력한다.

 

풀이 코드 

import java.io.*;

public class Main {

	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int g = Integer.parseInt(br.readLine());
		parents = new int[g+1];
		for(int i=1; i<g+1; i++) {
			parents[i] = i;
		}
		
		int p = Integer.parseInt(br.readLine());
		int cnt=0;
		for(int i=0; i<p; i++) {
			int l = Integer.parseInt(br.readLine());
			if(find(l) ==0) break;
			cnt++;
			union(find(l), find(l)-1);
		}
		System.out.println(cnt);
	}
    
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		parents[a] = b;
	}
	
	static int find(int x) {
		if(x == parents[x]) return x;
		return parents[x] = find(parents[x]);
	}
}