문제 링크

성능 요약

메모리: 23692 KB, 시간: 208 ms

분류

자료 구조, 분리 집합, 그리디 알고리즘

제출 일자

2025년 1월 24일 15:29:20

문제 설명

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

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

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

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

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

입력

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

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

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

출력

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

풀이

느낀점

• 가능한 높은 숫자의 게이트부터 채우는 것과, 도킹한 비행기 번호에 대해서 마지막으로 어느 위치에 도킹했는지를 기억해서 매번 비어있는 게이트까지 순회하는 시간을 줄여야겠다고는 생각했다.
• 그런데 연계된 부분까지 모두 마지막 위치를 저장하려고 순회해야 하기 때문에 빈곳을 찾는시간이나 값을 변경하는 시간이나 별 다르지 않다고 생각해서 다른 풀이를 슬쩍 참고했다…
• 분리집합 개념을 사용하지 않아도 풀 수 있다는 글도 있었지만, 이 문제를 보고 분리 집합을 떠올릴 수 있어야 한다는것이 스스로에게 실망스러웠다ㅠ 거의 다다랐는데 직접 풀어내지 못했다는 것이,,
• 어제오늘 푼 문제들이 활용할 알고리즘을 깨닫는 데에 어려움이 있었는데, 난이도가 올라갈수록 그런것 같다..

설계 : 30분

• 도킹할 위치는 비행기의 번호(순서와 별개)부터 1번까지의 게이트 중에만 선택할 수 있다.
• 작은 수일수록 선택지가 좁기 때문에 가능한 큰 숫자의 게이트부터 채우는 것이 좋다. (그리디)
• 도킹이 완료된 게이트는 해당 위치에 도킹하려는 다른 비행기에게 가능한 위치를 알려줘야 함으로 이걸 어떻게 효율적으로 저장하고 조회할 수 있는지 고민해야 한다.
• 여기서는 집합을 사용했다. 다음 도킹할 위치를 우두머리로 저장하여 연결한다.

코드(Java)

• 구현 시간: 25분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 공항_10775
 * Date: 2025.01.24
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] next;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int G = Integer.parseInt(br.readLine());
        next = new int[G+1];
        for (int i = 1; i <= G; i++) next[i] = i;
        int P = Integer.parseInt(br.readLine());
        int[] planes = new int[P];
        int answer = 0;
        for (int i = 1; i <= P; i++) {

            int plane = Integer.parseInt(br.readLine());
            int spot = findSet(plane);
            if (spot == 0) {
                answer = i - 1;
                break;
            }
            int to = findSet(spot-1);
            next[spot] = next[to];
        }
        if (answer == 0) answer = P;
        bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

    private static int findSet(int x) {
        if (next[x] == x) return x;
        return next[x] = findSet(next[x]);
    }
}