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

16566번: 카드 게임

---

 

문제풀이

 

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

 

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

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

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

 

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

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

---

코드

cpp

#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]);
‌}
}