[백준 16566] 카드 게임

 

 

 원래 분리 집합이랑 이진 탐색으로 푸는 문제인데, 나는 Red-Black Tree 이용하는게 먼저 떠올라서 C++의 set으로 풀었다. 전에 풀었던 공항 문제와 큰 차이가 없다.

 정석으로 풀자면, 카드를 정렬해두고 이진 탐색으로 조건에 맞는 값을 찾는 방법이지싶다. 사용한 카드는 다음 인덱스에 위치한 더 큰 카드와 Union 처리해서, 원래 오래걸리는 삭제 처리 대신에 Union Find 로직의 시간 복잡도만 이용하게 될테니 얼핏 생각해도 타당하다.

 

 내가 Red-Black Tree, 그러니까 C++ set을 사용하게 된 건 이론상 가능할 것 같아서였다. set에서 upper_bound를 찾아내는 것은 O(logM)만큼 걸릴 것이고, 찾은 노드를 삭제하는 과정도 O(logM)만큼 걸릴 것이다. 그리고 이 과정이 카드를 내는 K번의 동작 내내 일어나게 될 것이므로 O(K * (2 log M)) 가 걸릴 것이다. 그리고 처음 set을 구축하는 과정이 O(m log m)만큼 걸릴 것이므로, 이론상 시간 초과가 나지 않아야 한다.

 

 하지만 경험적으로 알다시피, C++의 set은 삽입과 삭제에서 기대하는 만큼의 성능을 보장하지 못하는 경우가 많기 때문에 처음에 작성했던 코드는 시간 초과를 받았다.

 set을 구축하는 과정에서, M번의 insert 연산을 이용한 것이 화근인 것 같았다. 그래서 vector를 M크기로 미리 할당해두고, 거기에 입력 받은 후에 정렬했다. 이후 set의 생성자에 정렬된 vector를 넣어서 생성하도록 변경했더니 꽤 빠듯하게 통과할 수 있었다.

 

 하드웨어 차원이나 언어적 차원에서 좀 더 최적화가 가능할지도 모르겠지만, 다음에 이런 문제를 보면 곱게 분리 집합과 이진 탐색을 떠올려서 푸는게 나을 것 같다..

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> cardVector(m);
    int num;

    for(int i=0; i<m; i++) {
        cin >> cardVector[i];
    }

    sort(cardVector.begin(), cardVector.end());

    set<int> cardSet(cardVector.begin(), cardVector.end());

    for(int i=0; i<k; i++) {
        cin >> num;

        auto ub = cardSet.upper_bound(num);
        cout << *ub << "\n";
        cardSet.erase(ub);
    }
}