[백준/자바] 10775번: 공항

문제

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

풀이

• 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있음
• P개의 비행기가 순서대로 도착할 예정
  • i번째 비행기를 1번부터 Gi번째 게이트 중 하나에 영구적으로 도킹
  • 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고 어떤 비행기도 도착할 수 없음
• 비행기를 최대 몇 대 도킹시킬 수 있는가?

처음 문제를 접근했을 때에는 도착하는 비행기의 번호에서 시작하여, 도킹할 수 있는 번호가 나올 때까지 탐색하였습니다.

	public static boolean parking(int num) {
		while (num-- > 0) {
			if (!parked[num]) {
				parked[num] = true;
				answer++;
				return true;
			}
		}
		return false;
	}

위와 같은 방식으로 찾으면 시간 초과가 발생하게 됩니다.
이 문제는 시간복잡도가 최대 O(G * P)가 나옵니다.
여기서 G와 P의 최댓값인 10의 5승이 나오게 되면 1초 안에 끝날 수 없게 되죠.

이를 해결하기 위해 위 메서드를 수정할 필요가 있습니다.

그래서 생각해낸 것이 Union-Find였습니다.
비행기가 도킹할 수 있는 위치는 비행기 번호 이하의 자연수입니다.
부모 배열을 자기 자신으로 선언 후, 도킹을 하게 되면 부모 - 1의 값으로 부모를 바꿔버리는 방법이죠

부모 배열 및 게이트 초기화

	private static void make() {
		parked = new boolean[G+1];
		p = new int[G+1];
		
		for (int i = 1; i <= G; i++) {
			p[i] = i;
		}
	}

• 처음 부모의 상태는 자기 자신을 가리키고 있어야 합니다.

Union-Find

	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]); // 경로 압축
	}
	
	private static void union(int a, int b) {
		p[find(a)] = find(b);
	}

• 다른 유니온 파인드 문제와는 달리, 사이즈 배열이 필요 없습니다.
• 결국 부모를 자기 자신 - 1 값으로 설정할 것이기 때문이죠

메인문

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		G = Integer.parseInt(br.readLine());
		P = Integer.parseInt(br.readLine());
		
		make();
		for (int i = 0; i < P; i++) {
			int g = Integer.parseInt(br.readLine()); // 도킹할 비행기 번호
			
			int x = find(g); // 비행기가 도킹할 게이트 번호
			if (x == 0) break; // 없다면 종료

			parked[x] = true; // 도킹
			answer++; // 도킹 횟수 + 1
			union(x, x-1); // 바로 앞 번호로 도킹할 번호 변경
		}
		
		System.out.println(answer);
	}

• parent가 0이라면 주차할 공간이 없다는 뜻이기 때문에, 문제 조건에 의하여 종료하면 됩니다.

코드

import java.io.*;

public class Main {
	static int G, P;
	static int[] p;
	static boolean[] parked;
	
	static int answer = 0;
	
	private static void make() {
		parked = new boolean[G+1];
		p = new int[G+1];
		
		for (int i = 1; i <= G; i++) {
			p[i] = i;
		}
	}
	
	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	
	private static void union(int a, int b) {
		p[find(a)] = find(b);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		G = Integer.parseInt(br.readLine());
		P = Integer.parseInt(br.readLine());
		
		make();
		for (int i = 0; i < P; i++) {
			int g = Integer.parseInt(br.readLine());
			
			int x = find(g);
			if (x == 0) break;

			parked[x] = true;
			answer++;
			union(x, x-1);
		}
		
		System.out.println(answer);
	}

}