백준 16566 - 카드 게임

문제 설명

철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.

1. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
2. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
4. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.

철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.

민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 M개의 카드가 주어지고 K개의 입력이 주어지면 M개의 카드 중 입력보다 큰 수중 가장 작은 수를 출력하면 된다.

이때, 한 번 출력한 카드는 버려야 한다.

 

문제는 생각보다 간단하다.

K[i]보다 큰 수를 찾아 출력하고 지우면 된다.

for (int i = 0; i < K; i++)
{
    auto pos = upper_bound(cards.begin(), cards.end(), submits[i]);
    cout << *pos << "\n";
    cards.erase(pos);
}

하지만 위와 같은 로직을 사용하면 시간 초과가 발생한다.

erase에서 시간이 많이 소요되기 때문이다.

이를 줄이기 위해 이미 사용한 카드는 사용하지 않도록 하는 다른 방법을 써야 할 것 같다.

 

한 번 사용한 카드를 다시 사용할 상황이 되면 그거보다 큰 카드 중 작은 카드를 고르면 된다.

2 3 4 5 7 8 9

카드가 위와 같은 상황일 때 1이 두 번 주어지면 2를 출력하고 3을 다음으로 출력하면 된다.

이때 2를 출력하고 나서 2의 다음을 3으로 지정해 놓으면 효율적으로 출력할 수 있다.

유니온 파인드 구조를 사용하면 이를 구현할 수 있다.

2를 출력할 때 2의 부모를 3으로 설정해 놓으면 된다는 뜻이다.

int Find(int idx)
{
	if (parents[idx] == idx) return idx;
	return parents[idx] = Find(parents[idx]);
}

void Union(int a)
{
	int p = Find(a);
	parents[a] = p + 1;
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M, K;
vector<int> cards;
vector<int> submits;

vector<int> parents;

int Find(int idx)
{
	if (parents[idx] == idx) return idx;
	return parents[idx] = Find(parents[idx]);
}

void Union(int a)
{
	int p = Find(a);
	parents[a] = p + 1;
}

int main()
{
	INPUT_OPTIMIZE;

	cin >> N >> M >> K;
	
	cards.resize(M);
	parents.resize(M);
	submits.resize(K);

	for (int i = 0; i < M; i++)
	{
		parents[i] = i;
	}

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

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

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

	for (int i = 0; i < K; i++)
	{
		auto pos = upper_bound(cards.begin(), cards.end(), submits[i]) - cards.begin();
		cout << cards[Find(pos)] << "\n";

		Union(pos);
	}

	return 0;
}

---