문제 링크

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.


문제

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

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

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

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

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

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ \(10^{5}\))가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ \(10^{5}\))가 주어진다.

이후 P개의 줄에 \(g_{i}\) (1 ≤ \(g_{i}\) ≤ G) 가 주어진다.

출력

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



접근 과정

도착하는 비행기가 도킹할 수 있는 게이트 중 가장 큰(가장 오른쪽의) 게이트만을 찾아 도킹하도록 구현하여 문제를 해결할 수 있을 것 같았다. 문제는 도킹할 수 있는 가장 큰 게이트를 찾는 방법이 중요한데 가장 간단하게는 도킹 가능한 범위 \(g_{i}\)에서 1까지 도킹 가능한 게이트가 있는지 확인해보는 방법이다. 하지만 이 방식은 \(g_{i}\)가 연속으로 입력되는 경우에 문제가 된다.. 만약 아래와 같은 입력이 들어오면

input
100000
100000
100000
100000
.
.
.
100000
100000

매번 100000번 인덱스에서 1번 인덱스 까지 도킹 가능한 게이트를 탐색할 것이다. 시간복잡도 O(\(N^{2}\))의 알고리즘으로 제한시간을 초과하게된다. 이에 대한 해결책을 고민하다보니 이전에 탐색했던 \(g_{i}\)에 대해 어디까지 탐색했는지를 기록해두면 동일한 \(g_{i}\) 입력시 탐색시간을 빠르게 줄일 수 있을 것 같았고 결과적으로 성공적으로 구현할 수 있었다.

다만 일반적인 경우에는 확실히 빨라졌으나 여전히 시간초과가 가능한 케이스가 있을 것으로 보이는데 10만에서 5만까지 입력후 99999~50001 까지 입력한다면 50000 * 50000번의 연산으로 시간초과가 발생할 여지가 있다.(처음과 끝 외에는 현재위치 - 1만을 기록하므로) 어쩌면 후에 재채점되어 틀린 문제로 이동할지도 모르겠다.


소스 코드

#include <cstring>
#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int gateCount, p;
    int goodDocking = 0;
    int gate[100001];
    
    std::memset(gate, -1, sizeof(gate));

    std::cin >> gateCount >> p;
    for (int i = 0; i < p; ++i) {
        int gi;
        std::cin >> gi;

        if (gi > gateCount) {
            gi = gateCount;
        }

        int nextGate = gi;
        while (nextGate != 0) {
            if (gate[nextGate] == -1) {
                gate[nextGate] = nextGate - 1;
                gate[gi] = nextGate - 1;
                ++goodDocking;
                break;
            }
            nextGate = gate[nextGate];
        }

        if (nextGate == 0) {
            break;
        }
    }

    std::cout << goodDocking;
    return 0;
}