[C++] 카드 게임 (백준 16566번)

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

 

#include <iostream>
#include <set>
using namespace std;

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

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

    set<int> blue;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        blue.insert(x);
    }

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        auto it = blue.upper_bound(x);
        cout << *it << '\n';
        blue.erase(it);
    }
}

(TLE)

단순히 수들을 set에 넣어두고 upper_bound로 수를 찾고 지워주고...를 반복하면 시간 초과를 받는다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> parent;

int find(int a) {
    if (parent[a] == a) return a;
    else return parent[a] = find(parent[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[a] = b;
}

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

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

    vector<int> blue(m);
    for (int i = 0; i < m; i++) cin >> blue[i];
    sort(blue.begin(), blue.end());

    parent = vector<int>(m);
    for (int i = 0; i < m; i++) parent[i] = i;

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        int tidx = upper_bound(blue.begin(), blue.end(), x) - blue.begin();
        int chosen = find(tidx);
        cout << blue[chosen] << '\n';
        if (chosen + 1 < m) unite(chosen, chosen + 1);
    }
}

(AC)

그래서 수를 삭제하는 연산 대신 그 수를 사용했다면 그 수 다음 수를 써야 한다고 표시해주는 작업을 유니온 파인드를 이용하여 해주었다. 나는 민수의 카드 배열 blue의 인덱스를 기준으로 유파를 해줬다. 아이디어 떠올리는 게 어렵다 ㅜ.ㅜ