[C++] 백준 16566 : 카드 게임

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

16566번: 카드 게임

 

 

 

 

1이상 4,000,000 이하의 수 $N$ 개를 입력받고 $K$개의 임의의 수 $k$를 입력 받았을 때, $N$ 개의 수에서 $k$ 보다 큰 수들 중 가장 작은 수를 출력하면 되는 문제이다. 따라서 입력받는 대로 모든 수를 정렬하고, upper_bound 로 만족하는 결과를 얻을 수 있는 set 의 자료 구조의 사용을 바로 떠올렸다.

 

 

 

 

set<int> s;
for (int i = 0; i < N; ++i) {
    int value; cin >> value;
    s.insert(value);
}

while (K--) {
    int k; cin >> k;
    auto it = s.upper_bound(k);
    cout << *it << "\n";
    s.erase(it);
}

 

 

 

 

 

하지만 채점 결과로 받은 결과는 "틀렸습니다". set은 기본적으로 RB Tree를 사용한 자료구조인데, 트리의 왼쪽 서브트리와 오른쪽 서브트리의 높이를 맞춰주기 위해 어떤 값이 삭제되면 그 균형을 맞추는 과정이 필요하다. 이 과정에서 모든 값들이 정렬되어 있기도 해야해서 전체적인 노드에 큰 변화가 생길 수 있게 된다. 그렇기에 실제로 삭제에 소요되는 시간복잡도는 O(lg N) 이더라도, 비교적 큰 시간을 요구하게 된다.

 

 

 

 

RB Tree (출처: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)

 

 

 

 

 

따라서 RB Tree를 사용하지 않고 다른 자료구조를 사용하여 동일한 역할을 수행하도록 해야한다. 값들이 정렬된 상태에서 이분탐색으로 빠르게 찾을 수 있어야 하며, 삭제된 값들은 무시하고 다음으로 큰 값을 찾도록 만들어야 한다. 그렇기 하기 위해 union-find 와 배열의 이분탐색으로 진행할 수 있다. 

 

 

 

 

union-find는 삭제된 값을 무시하고 다음으로 큰 값을 찾기 위함이며, 이분탐색은 빠르게 입력 $k$ 보다 큰 값을 찾기 위해서 사용한다. union-find 에서는 $k$ 값이 삭제되는 경우, $k$보다 크면서 가장 작은 index를 먼저 찾고(upper_bound), index의 parent를 index + 1 로 설정해줌으로서 다음으로 큰 값을 찾게 해준다. 

 

 

 

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define MAX 4'000'001

using namespace std;

vector<int> parent(MAX);
vector<int> arr;


int find_f(int x) {
    if (parent[x] == x) return x;
    else return find_f(parent[x]);
}


void union_f(int x, int y) {
    x = find_f(x);
    y = find_f(y);

    if (x != y) parent[x] = y;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // parent 초기화
    for (int i = 1; i < MAX; ++i) parent[i] = i;
	
    int n, m, k; cin >> n >> m >> k;

    arr.resize(m);
    for (int &e : arr) cin >> e;
    sort(arr.begin(), arr.end()); // 이분탐색을 위한 정렬
    
    while (k--) {
        int chulsu; cin >> chulsu;
        int index = upper_bound(arr.begin(), arr.end(), chulsu) - arr.begin();
        index = find_f(index);

        cout << arr[index] << "\n";
        union_f(index, index + 1); // 삭제된 것은 다음 index 로 연결
    }
    
    return 0;
}