[ 백준 / 10775 ] 공항 ( 자바 )

www.acmicpc.net/problem/10775

10775번: 공항

 

문제는 2가지로 풀이가 가능하다. Greedy를 통해서 푸는 방법, Union-Find로 푸는 방법이 있다.

 

1. Greedy

1초에 1억번 연산이 가능하다는 것에 근거하여, Greedy로 풀어서 최악의 경우가 되어도 시간초과가 되지 않는다.

 

2. Union-Find

union과 find에서 어떠한 연산을 해주어야 하나? union에서는 부모를 찾은 후, 부모보다 1 작은 값은 부모로 넣는다. 이것은 최대한 큰 게이트 번호에 비행기를 넣겠다는 의미이다. 그리고, 그 전에 find로 검사해, 부모의 값이 0인지 검사해야 한다. 0이라는 의미는 더이상 비행이가 들어갈 공간이 없다는 것을 의미한다. 따라서 0인 순간 그만 두어야 한다.

 

연산은 당연히 Union-Find가 Greedy보다 훨씬 빠르다.

 

1. Greedy

package bj;

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] array = new int[100001];
		int M = sc.nextInt();

		int answer = 0;
		boolean isFinished = true;
		for (int i = 0; i < M; i++) {
			int airplane = sc.nextInt();
			if(airplane>N) break;

			isFinished = true;
			for (int j = airplane; j >= 1; j--) {
				if (array[j] == 0) { // 비어있으면 넣고 끝
					array[j] = 1;
					isFinished = false;
					answer++;
					break;
				}
			}

			if (isFinished == true) {
				System.out.println(answer);
				return;
			}
		}
		
		System.out.println(answer);

	}

}

 

2. Union-Find

import java.util.Scanner;

public class Main {
	
	static int[] parent = new int[100001];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		for(int i=1;i<=N;i++) {
			parent[i] = i;
		}
		int answer = 0;
		
		int M = sc.nextInt();
		for(int i=0;i<M;i++) {
			int airplane = sc.nextInt();
			if(airplane > N) break;
			if(find(airplane)==0) break;
			else answer++;
			union(airplane);
		}
		System.out.println(answer);
	}
	
	public static int find(int x) {
		if(parent[x]==x) return x;
		else return parent[x] = find(parent[x]); 
	}
	
	public static void union(int x) {
		x = find(x);
		parent[x] = x-1;
	}
}