Boj 22877) 가위바위보 버블 정렬

문제

백준 22877

설명

그냥 봐서는 뭔가 감이 잡히지 않는 문제다. 하지만 이 문제는 브루트포스 코드와 랜덤데이터를 만들기가 쉽다. 그래서 몇번 간단히 시뮬레이션을 돌리면 규칙을 파악하기 용의하다.

규칙을 파악하기 좋은 예시로 다음이 있다.

SSRRRSSRPP
SSRRSSRRPP
SSRSSRRRPP
SSSSRRRRPP
SSSSRRRRPP
SSSSRRRRPP
SSSSRRRRPP

몇번 시뮬레이션을 돌리면 위처럼 카드뭉치가 대각선으로 앞으로 가는 결과만 나온다. 그래서 규칙은 A > B 이면서 XXXAAABBBBBXXXX 이런 식이 있을 때 T 번 진행한 결과는 B 블럭이 T 칸 앞으로가서 A 블럭과 섞인 것과 같다고 예상할 수 있다.

이렇게 추론한 규칙은 쉽게 증명할 수 있다.

1. ABXXX 가 BAXXX 로 바뀌었다고 하자. 이때 뒤로간 A 가 다시 움직일 수 있는 경우는 XXX 가 B 로 시작하는 경우 뿐이다. 한 회차에 B 블럭의 끝으로 움직이고 다음회차부터 더이상 움직일 수 없다.
2. 바뀐 A 이전의 카드는 A 이후로 갈 수 없다. 왜냐하면 A 와 교환가능한 카드는 B 뿐이라 앞서 교환된 A 와 교환될 수 없기 때문이다.
3. 그러므로 이후에는 B 카드가 A 를 한 횟수마다 한개씩 뒤으로 보내는 경우 뿐이다. N 회차면 최대 N 번 보낼 수 있다.

구현은 연속된 카드의 갯수를 세어서 한번에 카드의 갯수를 바꾸거나 새로 삽입하면 간단히 할 수 있다.

• 이때 앞에서 이동시킨 결과가 뒤쪽에 반영되므로 주의하자.
• 또한 deque 의 삽입 삭제는 앞뒤에서만 O(1) 임에 주의하자.

시간 복잡도

O(\(\mathrm{N}\))

코드

using ll = long long;

#define R 'R'
#define S 'S'
#define P 'P'
#define M '0'

inline bool Cmp(char a, char b)
{
	return (a == R && b == S) || (a == S && b == P) || (a == P && b == R) || b == M;
}

void Solve(const string& in, int T)
{
	list<pair<char, int>> datas; datas.push_back({ M, 1 });
	for (auto c : in)
	{
		if (datas.back().first == c) datas.back().second++;
		else datas.push_back({ c, 1 });
	}
	datas.push_back({ M, 0 });

	for (auto iter = ++datas.begin(); iter != datas.end() && iter->first != M; iter++)
	{
		auto prev = iter; prev--;
		auto post = iter; post++;
		if (Cmp(prev->first, iter->first))
		{
			int off = min(prev->second, T);
			prev->second -= off;
			if (prev->first == post->first)
				post->second += off;
			else
				datas.insert(++iter, { prev->first, off });
		}
	}

	for (auto& p : datas)
	{
		if (p.first == M) continue;
		for (int i = 0; i < p.second; i++)
			cout << p.first;
	}
}

int main(void)
{
	int n = 10, T = 5;
	string in;
	cin >> n >> T;
	cin >> in;
	Solve(in, T);
}