[QUADTREE] 쿼드 트리 뒤집기

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

 

풀이입니다. 🤔

 

import java.util.*;
 
public class Main {
    private static final String EMPTY = "", X_HEAD = "x";
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            String tree = scanner.next();
            System.out.println(reverse(tree, 0));
        }
    }
 
    // 시작 index 부터 존재하는 트리의 모양을 뒤짚어 출력한다.
    private static String reverse(String tree, int index) {
        String head = (tree.length() <= index) ? EMPTY : String.valueOf(tree.charAt(index));
        StringBuilder ret = new StringBuilder();
        ret.append(head);
        if (head.equals(X_HEAD)) {
            int accSize = 1;
            List<String> accReverse = new ArrayList<>();
            for (int i = 0; i < 4; ++i) {
                String acc = reverse(tree, index + accSize);
                accSize += acc.length();
                accReverse.add(acc);
            }
            ret.append(accReverse.get(2));
            ret.append(accReverse.get(3));
            ret.append(accReverse.get(0));
            ret.append(accReverse.get(1));
        }
 
        return ret.toString();
    }
}

 

문자열의 index 부터 시작하는 트리를 뒤짚는 부분문제를 생각합니다. 
큰 트리부터 재귀로 이 부분문제를 풀어나가면서 배치하도록 하면 쉽게 풀 수 있습니다. 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️