백준12919 : A와 B 2

https://www.acmicpc.net/problem/12919

12919번: A와 B 2

어제 재귀를 풀고 맛이 들렸다.

첨엔 S에 문자열을 붙여가면서 T를 찾아갔는데, 시간초과가 났다.
A개수 B개수 세가면서 플래그를 주다가,,
그냥 T에서 조건절에 따라서 문자열을 제거하며 S를 찾아주면 불필요한 문자열의 탐색 없이 빠르게 찾을 수 있겠구나를 깨달았다.

package BOJ;

import java.util.*;

public class BOJ12919 {
    private static String S;
    private static boolean flag;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextLine();
        String T = sc.nextLine();
        go(T);
        System.out.println(flag ? 1 : 0);
    }

    private static void go(String T) {
        if (T.length() < S.length() || flag) return;
        flag = S.equals(T);

        int tl = T.length();
        if (T.lastIndexOf('A') == tl - 1) {
            go(T.substring(0, tl - 1));
        }
        if (T.charAt(0) == 'B') {
            go(reverseString(T.substring(1, tl)));
        }
    }

    private static String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}