[백준/BOJ] 백준 16566번 : 카드 게임

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

16566번: 카드 게임

유니온 파인드를 이용해여 뽑힌 카드는 뽑을 수 있는 카드 중 방금 뽑힌 카드보다 쿤 숫자 중 가장 작은 것과 유니온 하는 방법을 통해 문제를 해결했다. 특정 숫자보다 큰 숫자 중 가장 작은것을 찾는 방법은 upper_bound를 이용했다.

 

코드

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

int n, m, k;
vector<int> selected_card;
vector<int>::iterator it;
vector<int>::iterator it2;
vector<int> player1;
vector<int> output;
vector<int> parent(4000002);

void Pre()
{
	for (int i = 0; i < 4000002; i++)
	{
		parent[i] = i;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

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

//v쪽으로 병합
void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	parent[u] = v;
}


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

	Pre();

	cin >> n >> m >> k;

	for (int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		selected_card.push_back(input);
	}

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

		player1.push_back(input);
	}

	selected_card.push_back(4000001); //this_output_card가 가장 큰 카드가 뽑히는것에 대비
	sort(selected_card.begin(), selected_card.end());

	for (int i = 0; i < k; i++)
	{
		it = upper_bound(selected_card.begin(), selected_card.end(), player1[i]);
		int this_output_card = (*it);
		this_output_card = Find(this_output_card); //이번에 낼 카드

		it2 = upper_bound(selected_card.begin(), selected_card.end(), this_output_card); //이번에 낼 카드보다 큰 카드중 가장 작은것을 찾는다
		int this_output_card_next = (*it2);
		this_output_card_next = Find(this_output_card_next);

		output.push_back(this_output_card);

		Merge(this_output_card, this_output_card_next);
	}

	for (int i = 0; i < output.size(); i++)
	{
		cout << output[i] << "\n";
	}

	return 0;
}