백준 10775 (공항)

문제

---

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

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

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

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

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

 

 

 

풀이

---

g_i의 가장 뒷부분 부터 도킹을 해야 많은 수의 비행기를 도킹 할 수 있기에 g_i의 위치에 도킹을 먼저 시도한다.

 

해당 부분의 gate 배열의 저장된 부모 노드수가 0 이 되면 더이상 1 ≤ g_i 사이에 도킹이 가능한 게이트가 존재하지 않는 것이므로 그 때까지의 갯수를 출력해주면 된다.

 

<전체 코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[] gate;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		int g = Integer.parseInt(bufferedReader.readLine());
		int p = Integer.parseInt(bufferedReader.readLine());
		
		gate = new int[g+1];
		for(int i = 0 ; i <= g ; i++) {
			gate[i] = i;
		}
		
		int count = 0;
		for(int i = 0 ; i < p ; i++) {
			int idx = Integer.parseInt(bufferedReader.readLine());
			
			int empty_gate = find(idx);
			
			if(empty_gate == 0 )
				break;
			else {
				count++;
				union(empty_gate, empty_gate-1);
			}
			
		}
		sb.append(count);
  
        System.out.println(sb);
        bufferedReader.close();
	}
	
	static int find(int n) {
		
		if(n == gate[n])
			return n;
		else
			return gate[n] = find(gate[n]);
	}
	
	static void union(int x, int y) {
		
		x = find(x);
		y = find(y);

		gate[x] = y;
	}
}