QUADTREE 쿼드 트리 뒤집기 / ALGOSPOT

• 문제링크 : https://algospot.com/judge/problem/read/QUADTREE
• 제출링크 : https://algospot.com/judge/submission/detail/654647

압축을 풀었다가, 압축을 다시 하는 방법으로 접근해서는 않됩니다. 시간도 너무 오래 걸리고, 사용하는 메모리 양도 너무 많습니다.
따라서, 압축을 풀지 않은 상태로 뒤집는 방법을 찾는 방향으로 접근해야 합니다.

우선 x 안에 x 가 또 있는 경우를 제외하고, 풀이를 알아 보겠습니다.
xwwbb 입력을 받았다고 하고, wwbb 부분을 c1, c2, 3, c4로 바꿔써 보겠습니다.
x, c1, c2, c3, c4 가 되구요, 이것을 문제에서 요구한 대로 뒤집어 보면
x, c3, c4, c1, c2 가 됩니다. 따라서 답은 xbbww가 됩니다.

문제를 풀기 위해서는 c1c4 에 x 로 시작하는 문자열이 들어 왔을 때, 이부분을 recursion으로 코딩해야 합니다.
왜냐하면, c1c4 부분에 x가 들어있을 수 있으며, [...xwbbxx...]\ 와 같은 문자도 가능 하기 때문에, x안에 x가 또 있을 수도 있는 문제의 규칙을, recursion메서드로 해결해야 합니다.

코딩에서 주의해야 할 부분은, c1에 x가 들어 있었다고 하면, c1부분이 모두 파싱이 끝날 때까지, c2가 어디서 시작하는지 알 수 없다는 점 입니다. 따라서, 메서드를 디자인 할 때, c1부분을 처리하는 메서드가, c2 에서 파싱할 스트링을 만들어주는 방식으로 코딩하는게 좋습니다.

Java 에서 String은 immutable 입니다. 메서드 안에서 만들어진 스트링을 파라미터로 받아 오려면, 길이가 0인 스트링 배열을 사용하건, StringBuilder를 사용해야 합니다.

import java.util.Scanner;

/**
 * QUADTREE 쿼드 트리 뒤집기 / ALGOSPOT
 * 문제링크 : https://algospot.com/judge/problem/read/QUADTREE
 * 제출링크 : https://algospot.com/judge/submission/detail/654647
 */
public class Main {
    Scanner sc = new Scanner(System.in);

    public void solve() {
        int T = sc.nextInt();
        sc.nextLine();

        for(int t=0; t<T; ++t) {
            String in = sc.nextLine();
            String r = run(in);
            System.out.println(r);
        }
    }

    public String run(String S) {
        if((S.charAt(0) != 'x') || (S.length() < 1))
            return S;

        String a = "";
        StringBuilder r = new StringBuilder("");
        a = reverse(S, r);
        return r.toString();
    }

    public String reverse(String S, StringBuilder strRtn) {
        StringBuilder[] ss = new StringBuilder[]{
                new StringBuilder(""),
                new StringBuilder(""),
                new StringBuilder(""),
                new StringBuilder("")};
        // 맨앞에 x 가 있기 때문에, x를 잘라내고.
        S = S.substring(1);
        S = parse(S, ss[0]);
        S = parse(S, ss[1]);
        S = parse(S, ss[2]);
        S = parse(S, ss[3]);


        strRtn.append('x');
        strRtn.append(ss[2]);
        strRtn.append(ss[3]);
        strRtn.append(ss[0]);
        strRtn.append(ss[1]);
//        strRtn = 'x' + ss[2] + ss[3] + ss[0] + ss[1];
        return S;
    }

    public String parse(String S, StringBuilder strRtn) {
        if(S.length() < 1)
            return "";

        String strRemained = "";

        if(S.charAt(0) == 'x') {
            strRemained = reverse(S, strRtn);
        }
        else {
            strRtn.append(S.charAt(0));
            strRemained = S.substring(1);
        }

        return strRemained;
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
}