[백준BOJ] 10775번 공항.java

 

백준 저지에서 공항을 자바를 통해 풀어 보았다. 

 

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

10775번: 공항

10775번 공항.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

10775번 공항 

문제

오늘은 신승원의 생일이다.
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

설명

비행기를 최대로 도킹하기 위해서 g번 비행기는 g번 게이트에 도킹하는게 가장 좋다. 만약 g번 게이트가 이미 도킹되어 있다면 g-1번 게이트에 도킹되어야한다. 즉 g번 비행기는 도킹 가능한 게이트 중 g에 가까운 게이트에 도킹되어야 한다.

 

가장 간단한 방법은 g번 비행기에 대해서 도킹 가능한 게이트를 g부터 1번 게이트까지 전부 확인하는 것이다. 하지만 이런 방법으로는 시간초과에 걸린다.

 

g번 비행기가 들어왔을 때 도킹 가능한 게이트 중 가장 큰 숫자를 갖는 게이트를 구해야한다. 예를 들어 3번 비행기, 2번 비행기가 들어왔다고 가정했을 때 3번 게이트와 2번 게이트가 도킹된다. 따라서 다음 비행기로 1,2,3번 중 어떤 비행기가 들어오던지 1번 게이트에 도킹된다. 즉 3개의 비행기가 같은 게이트를 가리킨다. 

 

이러한 특징을 통해 유니온 파인드를 적용할 수 있다. 게이트에 비행기가 도킹될 때마다 해당 번호의 비행기가 들어왔을 때 도킹 되어야하는 게이트를 가리키도록 배열에 저장한다. 비행기가 도착하면 해당 비행기가 도킹될 게이트를 찾고(find) 해당 번호의 비행기가 들어왔을 때 도킹되어야할 게이트를 가리키도록 배열을 수정(union)한다.

코드

//10775번 공항.java
package boj20211222;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 공항_10775 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
	public static void main(String[] args) throws NumberFormatException, IOException {
		int G = Integer.parseInt(br.readLine());
		int P = Integer.parseInt(br.readLine());
		int[] parent = new int[G+1];
		for(int i=0;i<=G;i++) {
			parent[i]=i;
		}
		
		int count=0;
		for(int i=0;i<P;i++) {
			int g = Integer.parseInt(br.readLine());
			int gate = find(g,parent);
			if(gate==0)break;
			count++;
			
			union(gate,gate-1,parent);
		}
		System.out.println(count);
	}
	
	static int find(int x, int[] parent) {
		if(x==parent[x]) {
			return x;
		}
		parent[x] = find(parent[x], parent);
		return parent[x];
	}
	static void union(int x, int y, int[] parent) {
		x = find(x,parent);
		y = find(y,parent);
		if(x!=y) {
			parent[x]=y;
		}
	}
}