백준 16566 카드 게임(C++)

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

16566번: 카드 게임

 

문제 유형: 이분탐색, Union-Find

 

 

문제 설명

먼저 설명하기전에 c++ 입출력 억까를 당했다..

문제를 설명하면 먼저 입력에 주어진 배열을 저장한다.

그리고 k개의 자연수가 주어졌을 때, 이분탐색의 응용중 하나인 Upper Bound를 사용하여, k다음으로 큰 수를 배열에서 찾고, 출력해준다.

그리고 출력한 수는 다시 쓸 수 없으므로 똑같은 수가 주어졌을 때 k다음으로 큰수 다음으로 큰수를 출력해줘야한다.

그러기 위해선, Union-Find를 사용하여, 그 수를 가르키게 만드는 것으로 구현했다..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int parent[4000001];
int n,m,k;
vector<int> arr;
int Find(int x){
    if(parent[x] ==x) return parent[x];

    return parent[x] = Find(parent[x]);
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x!=y){
        if(x>y) parent[y] = x;
        else parent[x] = y;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0;i<m;i++){
        int num;
        cin >> num;
        arr.push_back(num);
        parent[i] = i;
    }
    sort(arr.begin(), arr.end());
    int temp;
    for(int i = 0;i<k;i++){
        cin >> temp;
        int index = upper_bound(arr.begin(), arr.end(),temp) - arr.begin();
        int p = Find(index);
        cout << arr[p] << endl;
        Union(p, p + 1);
    }
    return 0;
}