백준 | 10775번. 공항 - 그리디 & 유니온 파인드 문풀

⬛ 백준 10775번. 공항 - 그리디 & 유니온 파인드 문풀

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

10775번: 공항

문제

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

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

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

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

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

입력

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

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

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

출력

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

---

💚 문제 접근 방식

• 이 문제에 어떻게 유니온 파인드를 적용할지 모르겠어서 많이 헤맸다.
• 우선은 각 비행기가 1번~ gi번까지의 게이트에 도킹이 한 번만 가능하다 했기 때문에, 최대한 많은 비행기가 도킹 가능하려면 최대한 (자기가 가능한 게이트 중 큰 게이트)에 도킹을 해야 한다.
• 이 문제는 G, P가 각각 10^5까지 올 수있어서 이중 for문을 돌면 시간 초과가 난다.
• 하지만, 첫 시도에는 감이 잘 안와서 이중 for문을 돌며 직접 해봤다.

이중for문 돌면 시간 초과 불가피함

public class Main {
	
	//실행 메인 	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int G = kb.nextInt();
		int P = kb.nextInt();
		
		List<Integer> list = new ArrayList<>();
		for(int i =0; i<P; i++) {
			int gi = kb.nextInt();
			list.add(gi);
		}
		
		int answer = 0;
		boolean[] visited = new boolean[G+1];
        
		for(int i=0; i<P; i++) {
			//가장 큰 경우만 확인함 
			int tmp = list.get(i);
			
			for(int j=tmp; j >= 0; j--) {
				if(j!= 0 && !visited[j]) {
					answer++;
					visited[j] = true;
					break;
				}else if(j != 0 && visited[j]) {
					continue;
				}else if(j == 0) {
					System.out.println(answer);
					return;
				}
			}
		}
	}
}

---

parent[i] 에 대한 정의 : 각 비행기가 도킹할 수 있는 가장 큰 게이트 넘버

예를 들어, 어떤 비행기가 1~(4)번 게이트에 도킹할 수 있다고 했을 때 parent[4] = 2 라면 해당 비행기는 2번에 도킹이 가능하다. (왜냐면, 태초에 parent[i] = i 로 초기화 했는데, 도킹 할 때마다, 이미 도킹된 게이트는 union 처리를 할 거니까)

그래서 union 처리를 할 때, 현재 비행기에 대한 게이트 gi 가 들어왔다면 if( find(gi) == 0) 인 경우 break를 걸고 (gi번 앞부분에 도킹 가능한 게이트가 없어서 0이 됐다는 소리이므로) 그게 아니라면 union( find(gi) -1, find(gi)) 에 처리하는데 이유는 가장 큰 게이트 번호가 도킹이 되어야 하므로 도킹 union 처리할 때 바로 앞 번호와 union 처리를 해서 결과적으로는 최대한 큰 값이 parent[] 에 담기도록 하기 위함이다.

유니온 파인드 적용 후 통과

💚 제출 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 10775번. 공항 - 
 * @author MYLG
 *
 */
public class Main {
	/**
	 * parent[i] : gi 비행기가 도킹할 수 있는 가장 큰 게이크 넘버가 담김
	 */
	static int[] parent; 
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a , int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] =a;
		}
	}
	
	//실행 메인 	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int G = kb.nextInt();
		int P = kb.nextInt();
		
		List<Integer> list = new ArrayList<>();
		for(int i =0; i<P; i++) {
			int gi = kb.nextInt();
			list.add(gi);
		}
		
		parent = new int[G+1];
		for(int i=1; i<=G; i++) parent[i] = i;
		
		int answer = 0;

		for(int i=0; i<P; i++) {
			//가장 큰 경우만 확인함 
			int gi = list.get(i);
			
			if(find(gi) == 0) break;
			
			union(find(gi)-1, find(gi));
			
			answer++;
		}
		
		System.out.println(answer);
	}
}

문제를 제대로 이해하기까지 오래 걸렸고, 솔직히 어느 부분에 유니온 파인드를 적용할 수 있는 건지 많이 헤맸다. 연습이 더 필요할 것 같다.