풀이
이 문제를 풀 수 있는 가장 무식한 방법은 주어진 그림의 쿼드 트리 압축을 풀어서 실제 이미지를 얻고 상하 반전한 뒤 다시 쿼드 트리 압축하는 것입니다. 물론 그림의 크기 제한이 매우 크기 때문에 무식한 방법으로 풀 수 없습니다. 이런 경우 대개 우리가 선택할 수 있는 접근 방법은 두 가지 입니다.
- 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
- 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작해서 최적화 해 나가기
둘 중 어느 접근이 맞는지 판단하기란 쉽지 않으며, 시행착오와 경험이 필요합니다. 그러나 둘 중 확실히 더 쉬운 것은 후자입니다. 그러니 우선은 압축을 어떻게 풀어야 할지에 대해 먼저 알아 봅시다.
쿼드 트리 압축 풀기
쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 가장 자연스럽습니다. 문자열 s의 압축을 해제해서 크기의 배열에 저장하는 함수 decompress()를 구현한다고 합시다. 기저 사례는 s의 첫 글자가 w나 b인 경우이고, 이때는 배열 전체에 해당하는 색을 칠하고 곧장 종료합니다. 만약 첫 글자가 x라면 decompress()는 s의 나머지 부분을 넷으로 쪼개 재귀 호출합니다. 이때 각 부분이 배열의 어느 부분에 저장되어야 하는지 지정하는 위치 오프셋 또한 전달해야합니다. void decompress(final String s, int row, int column, int size) 함수를 만들면 됩니다.
압축 문자열 분할하기
이렇게 생각하고 곧장 구현을 시작하면 s의 나머지 부분을 넷으로 쪼개기가 쉽지 않습니다. 각 부분의 길이가 일정하기 않기 때문이죠. 이를 해결하기 위해 다음 조각의 길이를 구하고 문자열을 잘라서 재귀 호출을 할 수 있습니다. 하지만 이 방식은 비슷한 일을 하는 두 개의 함수를 각각 작성하기 때문에 비효율적입니다.
이런 때 유용하게 써먹을 수 있는 패턴은 s를 미리 쪼개는 것이 아니라 decompress() 함수에서 '필요한 만큼 가져다 쓰도록' 하는 것입니다. decompress() 함수에 s를 통째로 전달하는 것이 아니라, s의 한 글자를 가리키는 반복자 인스턴스를 전달합니다. 이 반복자 인스턴스는 참조형으로 전달되기 때문에 decompress() 함수가 종료하고 나면 반복자 인스턴스는 항상 다음 부분의 시작 위치를 가리키게 됩니다.
// 압축 해제하는 함수입니다.
public static void decompress(StringCharacterIterator it, int row, int column, int size) {
// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
char head = it.current();
it.next();
// 기저 사례: 첫 글자가 b 또는 w인 경우
if (head == 'b' || head == 'w') {
for (int dr = 0; dr < size; dr++) {
for (int dc = 0; dc < size; dc++) {
decompressed[row + dr][column + dc] = (head == 'b' ? 1 : 0);
}
}
} else {
// 네 부분을 각각 순서대로 압축 해제한다.
int half = size / 2;
decompress(it, row, column, half);
decompress(it, row, column + half, half);
decompress(it, row + half, column, half);
decompress(it, row + half, column + half, half);
}
}이 함수는 그림의 크기를 요구하므로 그림의 크기를 구하는 함수를 작성합니다.
// 압축된 그림의 크기를 구하는 함수입니다.
public static int getSize(String compressed) {
StringCharacterIterator it = new StringCharacterIterator(compressed);
int depth = getDepth(it, 0);
return (int) Math.pow(2, depth);
}
// 압축된 그림의 크기를 알기 위해 압축된 깊이를 찾는 함수입니다.
public static int getDepth(StringCharacterIterator it, int depth) {
char head = it.current();
it.next();
int maxDepth = depth;
if (head == 'b' || head == 'w') {
return depth;
} else {
maxDepth = Math.max(getDepth(it, depth + 1), maxDepth);
maxDepth = Math.max(getDepth(it, depth + 1), maxDepth);
maxDepth = Math.max(getDepth(it, depth + 1), maxDepth);
maxDepth = Math.max(getDepth(it, depth + 1), maxDepth);
}
return maxDepth;
}그림을 압축한 문자열이 xbwxwbbwb라면 그림을 압축 해제 했을 때
이렇게 됩니다. 하지만 그림의 최대 크기는 이므로 압축을 풀기에 너무 큽니다.
압축 다 풀지 않고 뒤집기
그림의 크기 때문에 압축을 풀지 않고 뒤집는 방법을 생각해내야 합니다. 이 방법은 전체가 검은색이나 흰 색인 그림은 뒤집어 봤자 다를 게 없다는 사실을 안다면 쉽게 구현할 수 있습니다.
전체가 한 가지 색이 아닌 경우에는 재귀 호출을 이용해 네 부분을 각각 상하로 뒤집은 결과를 얻은 뒤, 이들을 병합해 답을 얻어야 합니다.
// 압축을 해제하지 않고 뒤집는 알고리즘
public static String reverse(StringCharacterIterator 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() 함수는 한 번 호출될 때마다 주어진 문자열의 한 글자씩을 사용합니다. 따라서 함수가 호출되는 횟수는 문자열의 길이에 비례하므로 이 됩니다. 각 문자열을 합치는 데 의 시간이 든다 해도 시간 안에 충분히 수행할 수 있습니다.
회고
StringCharacterIterator 클래스를 처음 알게 되었습니다.
getDepth() 함수가 decompress() 함수와 비슷한데 decompress() 함수의 인자로 넣을 값을 얻기 위해 비슷한 함수인 getDepth() 함수를 구현한 것이 왠지 비효율적으로 느껴지지만 그렇다고 다른 더 효율적인 방법을 떠올릴 순 없었습니다.
