7.2 쿼드 트리 뒤집기(ID : QUADTREE)
제출일 : 2021-01-12
문제 풀이 시간 : 1H 30M
문제
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.
- 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이
b가 됩니다. - 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이
w가 됩니다. - 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는
x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은xwwwb로 압축됩니다.
그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.
쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.
입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 $2^{20} × 2^{20}$ 을 넘지 않습니다.
출력
각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.
예제
입력
4
w
xbwwb
xbwxwbbwb
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb출력
w
xwbbw
xxbwwbbbw
xxwbxwwxbbwwbwbxwbwwxwwwxbbwb문제 풀이 접근
풀이가 떠오르지 않아 QuadTree 클래스를 만들어 단순하지만 무식한 방법으로 해결하려 접근하였습니다. 하지만 각 부분의 길이가 일정하지 않기 때문에 쪼개기가 까다로웠고 다른 풀이방법을 생각해야 했습니다.
이 문제를 분할하여 상하 반전을 한 값을 다시 병합했을때 결과가 정답이 된다는 것을 확인하고 아래와 같이 코드를 작성하였습니다.
코드
언어 : JAVA
실행 시간 : 156ms
import java.util.Scanner;
public class Main {
static String str;
static int pointer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int C = sc.nextInt();
for (int tc = 0; tc < C; tc++) {
str = sc.next();
pointer = 0;
System.out.println(reverse());
}
}
private static String reverse() {
if (str.charAt(pointer) != 'x') {
return "" + str.charAt(pointer++);
}
pointer++;
String one = reverse();
String two = reverse();
String three = reverse();
String four = reverse();
return 'x' + three + four + one + two;
}
}'Problem' 카테고리의 다른 글
| 6.8 시계 맞추기 (ID : CLOCKSYNC) (0) | 2021.01.09 |
|---|---|
| 6.5 게임판 덮기(ID : BOARDCOVER) (0) | 2021.01.05 |
| 6.3 소풍 (0) | 2021.01.03 |
)
