[백준 10775] 공항

 

 그리디 알고리즘과 분리 집합을 활용하는 문제..이지만 나는 그리디와 자료구조를 이용해서 풀었다. 풀고나서 다른 접근법을 찾아보다가 분리 집합을 이용한 풀이를 봤는데, 저렇게도 접근할 수 있었구나 싶어서 재밌었다.

 

 문제에도 나와있듯이, 비행기 번호는 1번 게이트부터 해당 번호의 게이트까지 도킹할 수 있음을 의미한다. 따라서 각각의 비행기는 가능한 가장 번호가 큰 게이트에 도킹하는 것이 무조건 유리한 상황이고, 그리디 알고리즘을 적용할 수 있음을 생각할 수 있다.
 비행기의 수가 최대 10^5대까지 입력으로 들어올 수 있고, 게이트의 수도 최대 10^5개까지 존재할 수 있다. 나이브하게 생각하자면, 비행기 하나하나에 대해 게이트 목록을 선형 탐색해 빈 게이트 중 선택할 수 있는 가장 큰 번호의 게이트를 찾는 로직인데 이는 O(P*G)에 해당하므로 시간 초과가 발생한다.
 비행기를 도착하는 순서대로 처리해야하므로, 비행기를 차례대로 선형 탐색하게 되는 과정은 필연적이고 그렇다면 적절한 게이트를 찾아내는 과정을 O(log G) 이내로 처리하는 것이 바람직하다.

 그래서 몇 가지 자료구조와 알고리즘의 조합을 떠올려보았다.

 

1. Array List + 이진 탐색 : 비행기 번호 이하의 게이트 번호를 빠르게 찾아낼 수 있지만, 이미 게이트에 도킹되어 있는 비행기가 있는 지 여부를 선형 탐색으로 추가적으로 판단해야한다. 최악의 경우 결국 O(n)만큼 걸리므로 개선이 되지 않는다.
2. Array List + 이진 탐색 + a : 리스트에서 도킹된 게이트 삭제하기(O(n)), 비행기 도킹을 완료할 때마다 도킹 정보와 게이트 번호를 기준으로 재정렬하기(O(n log n)) 등 몇 가지 추가적인 보조 로직을 떠올렸으나 모두 적합하지 않았다.
3. Linked List : 리스트에서 도킹된 게이트의 삭제가 O(1)에 해당하지만, Linked List에서는 이진 탐색을 활용할 수 없다. 따라서 적절한 게이트 번호를 탐색하는 과정에서 O(n)이 소요된다. 추가적인 메모리 공간을 할당해 굳이굳이 이진 탐색을 진행할 순 있지만, 그 방법도 최악의 경우 O(n)에 해당한다.

4. Priority Queue, Heap: 우선순위가 비행기 번호에 따라 동적으로 변하므로 매번 힙을 재구축 해야해서 O(n)이 추가적으로 걸린다.

 하지만 생각해보니 탐색도 O(log n)만에 하고 삭제도 O(log n)만에 할 수 있는 자료구조가 있었다. 바로 이진 탐색 트리(BST, Binary Search Tree)다. 게이트를 나타내는 초기 트리는 결국 내가 임의로 구축하니까, 조금 신경쓴다면 순수한 이진 탐색트리를 사용해도 상관 없겠지만 나는 C++ STL에서 제공하는 잘 구성된 자가 균형 이진 탐색 트리를 사용하기로 했다.

 

 set 라이브러리를 사용했는데, 이는 내부적으로 레드-블랙 트리를 기반으로 구현되어 있기 때문에 내가 트리의 형태를 따로 신경쓰지 않아도 언제나 O(log n)의 탐색 및 삭제를 보장한다. 

 이를 사용해서 매번 비행기 번호 값을 가지고 Upper Bound를 찾아, 그 이전 노드(입력된 비행기 번호보다 크지 않은 노드가 된다)를 참조해서 도킹(삭제) 처리 해준다. 그러면 O(log n) + O(log n)으로, 결과적으로 O(log n)에 해당한다. 만약 Upper Bound를 찾았는데 가장 첫 노드이면 더 이상 도킹할  수 있는 게이트가 없는 것이며, 비행기의 수가 게이트의 수보다 더 많을 수 있으므로 set의 크기가 비어있지 않았은도 항상 확인해준다.

 

 입력받는 비행기의 수만큼 탐색 및 삭제를 반복하므로 전체 시간복잡도는 O(P log G)에 해당하며, 시간 내에 문제를 해결할 수 있었다. 

#include <iostream>
#include <set>

using namespace std;

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

    int g, p, planeNum;
    cin >> g >> p;

    set<int> gateSet = set<int>();
    
    for(int i=1; i<=g; i++) {
        gateSet.insert(i);
    }

    int dockedNum = 0;
    bool flag = true;

    for(int i=0; i<p; i++) {
        cin >> planeNum;
        
        if(flag) {
            auto iter = gateSet.upper_bound(planeNum);
            
            if(gateSet.empty()) {
                flag = false;
            } else if(iter != gateSet.begin()) {
                iter--;
                gateSet.erase(iter);
                dockedNum++;
            } else {
                flag = false;
            }
        }
    }

    cout << dockedNum;
}