[백준 - 10775번] 공항 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디

입력

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

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

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

출력

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

풀이

구하고자하는 것은 최대 도킹 횟수이다.

도킹 횟수를 최대로 하려면 가능한 게이트 범위에서 가장 뒤에 위치시켜야 한다.
그래야 도킹 가능성을 최대로 높일 수 있기 때문이다.

예를 들어 gi가 4라면 1~4 범위고, 4게이트에 도킹하는 것이 최선의 선택이 된다.
만약 4게이트가 차있다면 바로 앞 게이트인 3게이트에 도킹하는 것이 최선이다.

그런데 비행기마다 가능한 범위를 전부 탐색한다면 시간 초과다.

그래서 가능한 범위 중 가장 뒤에 있는 게이트를 어떻게 효율적으로 찾는지가 중요하다.

내가 생각한 방식은 다음과 같다.

게이트마다 다음번 최선의 게이트 번호를 저장하는 것이다.

예를 들어 4번 게이트에 처음 도킹하면 다음 최선의 게이트는 3이기 때문에 3을 저장하는 것이다.

이렇게만 하면 사실 모든 범위를 탐색하는 것과 다르지 않다.

그래서 업데이트 작업을 추가적으로 해야한다.

최초의 탐색은 최대 10만이 될 수 있다. 이 탐색 과정에서 최선의 게이트를 찾았다면, 탐색한 모든 게이트의 찾은 최선의 게이트 번호를 저장하는 것이다.

그러면 P를 반복하면서, 이미 탐색한 게이트는 다음 탐색에 제외되기 때문에 O(G + P)로 풀 수 있다.

풀이만 보면, 이해하기 어려울 수 있다. 꼭 그림으로 그려가면서 해보는 걸 추천한다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int G, P;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        G = Integer.parseInt(br.readLine());
        P = Integer.parseInt(br.readLine());
        
        int[] gate = new int[G + 1];
        int answer = 0;
        for(int i=0; i<P; i++) {
            int maxGate = Integer.parseInt(br.readLine());
            if(!docking(gate, maxGate)) {
                break;
            }
            answer += 1;
        }
        System.out.println(answer);
    }
    
    static boolean docking(int[] gate, int maxGate) {
        int cursor = maxGate;
        while(gate[cursor] != 0) {
            if(gate[cursor] == -1) {
                return false;
            }
            cursor = gate[cursor];
        }
        int newGate = cursor == 1 ? -1 : cursor - 1;
        
        for(int i=cursor; i<=maxGate; i++) {
            gate[i] = newGate;
        }
        
        return true;
    }
}