[algospot][분할정복] 쿼드 트리 뒤집기 : https://www.algospot.com/judge/problem/read/QUADTREE

QUADTREE.cpp

#include<iostream>
#include<string>
#include<vector>

/*
 * 시간복잡도 : O(N)
 * 공간복잡도 : O(N)
 */

using namespace std;

pair<string,int> solve(string s, int ind) {

	vector<string> arr;
	if (s.size() == 1)
		return { s, 1 };

	// if s.size() not zero -> must s[0] == 'x'.
	string answer = "x";
	ind++;

	for (; ind < s.size(); ind++) {
		if (arr.size() == 4)
			break;
		char now = s[ind];
		if (now == 'w')
			arr.push_back("w");
		else if(now == 'b')
			arr.push_back("b");
		else { // x
			pair<string, int> next = solve(s, ind);
			ind = next.second - 1; // because of ind++ when for statement
			arr.push_back(next.first);
		}
	}

	answer += arr[2] + arr[3] + arr[0] + arr[1];
	return { answer, ind };
}

int main() {
	int N;
	cin >> N;
	while (N--) {
		string input;
		cin >> input;
		cout << solve(input,0).first << endl;
	}
	return 0;
}