[백준] 16566번: 카드 게임

📌 문제

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

📌 설명

철수가 내는 카드보다 민수가 내는 카드의 번호가 더 크도록 해야 한다. 즉, M개의 주어진 카드에서 철수가 낸 카드의 번호보다 큰 최소의 번호를 내야 한다. 이 부분에서 이분 탐색으로 해결해야 함을 알 수 있다.

set을 통해 M개의 카드를 관리하고 upper_bound()를 통해 최적의 카드 번호를 출력하고 erase()하는 방법으로 작성하였다. 그러나 이 방법은 시간초과가 발생했다. 코드를 다 작성하니 300 비트 정도였는데, 작성일 기준 플레티넘 5 등급의 문제가 이 정도로 풀리는 게 말이 안 되긴 하다. 찾아보니 set은 이진 트리의 일종인 레드-블랙 트리로 원소를 관리하기 때문에 N이 클 경우 삽입 및 삭제에서 큰 오버헤드가 발생한다고 한다.

알고리즘 분류 탭을 참고하니, 이진 탐색으로 접근하는 것은 맞으나 분리 집합을 추가로 사용하여 해결하는 문제였다. 민수는 낸 카드를 다시 사용할 수 없으므로 이에 대한 처리를 해야 한다. 예를 들어 낼 수 있는 카드가 3, 5, 6이라고 하고, 3을 냈다고 하자. 다음 턴에 낼 수 있는 최적의 카드가 3이라고 하면 3 대신 5를 내야 한다. 따라서 카드를 낸 후 다음 카드와 Union을 하여 번호 3인 카드에 접근하더라도 그 다음 카드인 5를 내도록 해야 한다.

📌 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int parent[4000001];

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

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x < y) {
		parent[x] = y;
	}
	else
		parent[y] = x;
}

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

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

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	vector<int> v;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	sort(v.begin(), v.end());

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

		int idx = upper_bound(v.begin(), v.end(), x) - v.begin();
		int card_idx = Find(idx); // 실제로 내야 하는 카드의 인덱스
		cout << v[card_idx] << "\n";

		// 다음에 현재 낸 카드를 다시 내야한다면 그 다음으로 큰 수의 카드를 내야 함. 따라서 현재 카드와 다음 카드를 Union
		Union(Find(card_idx), Find(card_idx) + 1);
	}
}