핵심

• 처음에는 A,B 개수만 가지고 가지치기하려고 했는데, 이렇게하니까 시간초과가 떴음.
  • 아직도 가지치기에 대한 시간복잡도 계산을 하는 것은 너무 어렵다..
• S에서 T를 만들어보는 게 아니라 T에서 S를 만드는 것이 훨씬 많은 경우의 수를 줄여준다는 것을 깨닫고 풀이를 변경
  • B가 처음에 있거나 A가 마지막에 있는 경우만 고려하면 됨.
• 다른 분들 풀이를 차후에 보니 StringBuilder로 reverse 시키는 것도 되게 빨랐음.
  • 왜 시간 차이가 안나는지는 모르겠다. 글자 수가 적어서 그런가..?
  • 나는 인덱스로 하나하나 거꾸로 바꿔가면서 생각했는데 음

코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Algo12919 {

    private static String s, t;
    private static boolean canMake = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        t = br.readLine();
        backTracking(true, 0, t.length() - 1);
        if (canMake) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static void backTracking(boolean isForward, int start, int end) {
        if (end - start + 1 < s.length() || canMake) return;

        if (end - start + 1 == s.length()) {
            canMake = isSameString(isForward, start, end);
        }
        if (isForward) {
            if (t.charAt(start) == 'B') {
                backTracking(false, start + 1, end);
            }
            if (t.charAt(end) == 'A') {
                backTracking(true, start, end - 1);
            }
        } else {
            if (t.charAt(start) == 'A') {
                backTracking(false, start + 1, end);
            }
            if (t.charAt(end) == 'B') {
                backTracking(true, start, end - 1);
            }
        }
    }

    private static boolean isSameString(boolean isForward, int start, int end) {
        if (isForward) {
            for (int i = start; i <= end; i++) {
                if (s.charAt(i - start) != t.charAt(i)) {
                    return false;
                }
            }
        } else {
            for (int i = end; i >= start; i--) {
                if (s.charAt(end - i) != t.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}