[백준 C++] 16566 카드 게임 - 분리집합

16566번: 카드 게임

---

 

문제풀이

 

이분 탐색, 유니온-파인드 연산을 이용해서 푸는 문제입니다.

 

민수의 카드를 오름차순 정렬하고 upper_bownd 함수(이분 탐색)를 사용해서 내야하는 카드를 찾아 출력하면 됩니다.

그런데 한 번 낸 카드는 다시 낼 수 없기 때문에 다음 탐색에서는 제외해야 합니다.

카드의 총 개수가 많기 때문에 이 때 원소를 삭제하는 방식으로 풀면 시간초과가 발생합니다.

 

따라서 유니온-파인드 연산을 이용해서 한번 낸 카드는 다음 인덱스의 카드와 연결(크기가 큰 카드를 부모로 지정)해주고,

다음 번 중복 카드 탐색이 발생했을 때, 연결된 카드 중 가장 큰 카드(아직 내지 않은 카드)를 출력하도록 구현하면 됩니다.

---

코드

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

int N, M, K;
int Blue[4000001];
int Root[4000001];

int Find(int Node)
{
	if (Node == Root[Node])
	{
		return Node;
	}

	return Root[Node] = Find(Root[Node]);
}

void Union(int NodeA, int NodeB)
{
	int A = Find(NodeA);
	int B = Find(NodeB);
	int Max = max(A, B);
	Root[A] = Max;
	Root[B] = Max;
}

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

	cin >> N >> M >> K;

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

	sort(Blue, Blue + M);
	for (int i = 0; i < M; ++i)
	{
		Root[Blue[i]] = Blue[i];
	}

	for (int i = 0; i < K; ++i)
	{
		int Red;
		cin >> Red;

		int Index = upper_bound(Blue, Blue + M, Red) - Blue;
		int Num = Find(Blue[Index]);
		cout << Num << '\n';

		int NewIndex = lower_bound(Blue, Blue + M, Num) - Blue;
		Union(Blue[NewIndex], Blue[NewIndex + 1]);
	}
}