📝문제

다양한 방법을 시도해봤다.
이 문제를 풀 때 조심해야 할 것은 s부터 출발하여 t를 만드는 완전탐색의 방법을 택하면 시간초과나 메모리초과가 발생한다는 것이다.
시간복잡도가 O(2^n)이기 때문에...
따라서 t에서 출발하여 주어진 조건에 따라 문자를 삭제해가며 s가 나올 수 있는지 탐색해야한다.
이렇게 한다며 불필요한 경우의 수를 제거할 수 있다.

📌코드

package Solving;

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

public class BOJ12919 {
    /**
     * 두가지 경우를 recursive하게 탐색 -> 시간초과
     * 1. StringBuilder를 이용한 reverse()는 시간초과
     * 2. for문을 활용한 뒤집기는 시간초과
     *
     * BFS를 사용하여 탐색 -> 메모리초과
     *
     * t에서 주어진 경우에 따라 문자열을 제거하면서(재귀) s가 나오는지 확인
     *
     */

    static boolean answer = false;
    static StringBuilder sb;

    static void recur(String s, String t){
        // stop condition
        if(s.equals(t)) {
            answer = true;
            return;
        }
        if(s.length() >= t.length()) return;

        // t의 끝자리가 A인 경우
        if(t.charAt(t.length()-1) == 'A'){
            recur(s, t.substring(0, t.length()-1));
        }
        // t의 첫번째 글자가 B인 경우
        String temp = "";
        if(t.charAt(0) == 'B'){
            // 뒤집고 B를 제거
            sb = new StringBuilder(t);
            temp = sb.reverse().toString().substring(0, t.length()-1);
            recur(s, temp);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();

        recur(s, t);

        System.out.println(answer ? 1 : 0);
    }
}