분할 정복 - 1. 쿼드 트리 뒤집기

문제 : 쿼드 트리 뒤집기 (난이도 下)

 

https://algospot.com/judge/problem/read/QUADTREE

 

분석

 

문제를 읽다 보면 자연스레 압축을 푼 뒤 뒤집는 순으로 문제를 해결해야겠다고 설계하게 된다.

그러나 압축을 푸는 과정에서 트리의 사이즈를 잡는데 뭔가 복잡하고 이상하다.

'x'가 일정 범위 내에서 몇 번 나오냐에 따라 사이즈가 정해지는데 이걸 재귀 호출로 구현하기가 만만치 않다.

또한 최대 그림 크기가 2^20 x 2^20 인데 이는 1TB에 가깝기 때문에 압축을 풀어 푼다는 것은 불가능에 가깝다.

 

그럼 어떻게 문제를 해결해야 할까? 

문제를 다시 보니 그림을 상하만 바꾸면 된다. 그럼 압축을 다 풀지 않고 뒤집을 수 있을까?

 

 

그림을 보면, 상하간의 데이터만 바뀌고 좌우 데이터는 유지되는 것을 알 수 있다.

따라서 좌우 데이터를 유지한 채 상하 데이터만 바꾸면 문제를 보다 쉽게 해결할 수 있다.

 

구현

using namespace std;

string reverse(string::iterator& it)
{
	char head = *it;
	it++;
	//base case
	if (head == 'b' || head == 'w')
	{
		return string(1, head); //slicing data
	}
	string upper_left = reverse(it);
	string upper_right = reverse(it);
	string lower_left = reverse(it);
	string lower_right = reverse(it);
	return string("x") + lower_left + lower_right + upper_left + upper_right;
}

int main()
{
	int C;
	cin >> C;
	while (C--)
	{
		string inpute_data;
		cin >> inpute_data;
		
		string::iterator it = inpute_data.begin();
		cout << reverse(it) << '\n';
	}
	return 0;
}

 

시간 복잡도

 

문자열 길이에 따라 수행 시간이 결정된다.

-> O(n)

 

회고

 

문제를 접근할 때 복잡하다 싶음, 다른 시각으로 보는 것도 중요한 것 같다.