[JAVA] 백준 10775번 : 공항

 

---

 

• 생각

1. 문제를 일고 처음에 이해가 되지 않았는데, 예제를 보고선 도킹을 할 때 현재 번호보다 낮은 번호에만 도킹을 할 수 있다는 사실을 알게되었다.

 

• 코드

정답 코드 : gate[index] == index 일때만 도킹을 해준다. 도킹을 했을댄 index의 값을 -1해줘서 해당 인덱스에는 다신 도킹할 수 없게 하였다. gate[index] != index 경우에는 해당 게이트보다 낮은 게이트를 재귀로 모두 다 돌아본 다음 도킹 가능한 게이트가 있으면 도킹, index가 0까지 가는 경우 도킹을 종료한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int G, P;
	static int[] gate, airplane;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMaxValue());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		G = Integer.parseInt(br.readLine());
		P = Integer.parseInt(br.readLine());
		gate = new int[G + 1];
		airplane = new int[P + 1];

		for (int i = 1; i <= G; i++)
			gate[i] = i;

		for (int i = 1; i <= P; i++)
			airplane[i] = Integer.parseInt(br.readLine());
	}

	private static int FindMaxValue() {
		int count = 0;

		for (int i = 1; i <= P; i++) {
			if (docking(airplane[i]) < 0)
				break;
			count++;
		}

		return count;
	}

	private static int docking(int index) {
		// basecase (게이트 번호의 값이 0이면 도킹 불가)
		if (gate[index] == 0)	return -1;
		
		if (gate[index] == index)	// 도킹을 아직 시도하지 않은 게이트라면
			gate[index]--;
		else						// 도킹을 한 게이트라면 현재 게이트보다 낮은 게이트를  찾기 위해 재귀를 돔.
			gate[index] = docking(gate[index]);
		
		return gate[index];
	}
}