[분할 정복] 쿼드 트리 뒤집기(convert quad tree)

 

입력

쿼드 트리로 압축한 그림이 주어진다.

모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 2^20*2^20을 넘지 않는다.

 

 

예제 입력

xbwwb
xbwxwbbwb

 

예제 출력

xwbbw
xxbwwbbbw

 

코드

포인트는 위 그림!

첫 번째 그림을 뒤집는 과정을 1) 숫자를 각자 뒤집고 2) 아래와 위를 뒤집는 걸로 생각한다.

 

전체가 검은색이나 흰 색인 그림은 뒤집어봤자 다를 게 없기 때문에 b, w는 그대로 리턴한다.

CharacterIterator를 사용하는 이유도 잘 생각해 보면 좋을듯

import java.text.CharacterIterator;

public class QuadTree {
	String reverse(CharacterIterator it) {
		char head = it.current();
		it.next();

		if (head == 'b' || head == 'w')
			return Character.toString(head);

		String upperLeft = reverse(it);
		String upperRight = reverse(it);
		String lowerLeft = reverse(it);
		String lowerRight = reverse(it);

		return "x" + lowerLeft + lowerRight + upperLeft + upperRight;
	}
}

 

시간 복잡도

reverse()는 호출 시 주어진 문자열의 한  글자씩만  사용한다.

따라서 함수 호출 횟수는 문자열의 길이에 비례하므로 O(n)이고 각 문자열을 합치는데 O(n)의 시간이 든다. = 시간 충분

 

 

References 

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략