백준 12919 A와 B 2

문제

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

---

입출력

---

예제

---

태그

• 구현
• 문자열
• 브루트포스 알고리즘
• 재귀

---

풀이

• T의 글자를 뒤에서부터 하나씩 제거하면서 S와의 길이가 같아질 때까지 비교한다.
• T의 맨 끝 글자가 A이면 그 글자 A를 제거한다.
• T의 맨 앞 글자가 B이면 그 글자 B를 제거하고 뒤집어준다.

---

코드

정답 코드

/**
 * 12919_A와 B 2
 *
 * T의 글자를 뒤에서부터 하나씩 제거하면서 비교한다.
 * T의 맨 끝 글자가 A이면 그 글자 A를 빼준다.
 * T의 맨 앞 글자가 B이면 그 글자 B를 빼주고 뒤집어준다.
 *
 * S와 T의 길이가 같고 S==T일 경우 1을 반환한다.
 */
public class P_12919 {
    static String S, T;

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

        int result = dfs(S, T);

        System.out.println(result);
    }

    static int dfs(String s, String t){
        if(t.length() == s.length()){
            if(t.equals(s)){
                return 1;
            }
            return 0;
        }

        int ans = 0;
        if(t.charAt(t.length() - 1) == 'A'){
            ans += dfs(s, t.substring(0, t.length()-1));
        }

        if(t.charAt(0) == 'B'){
            StringBuilder reverse = new StringBuilder();
            reverse.append(t.substring(1));
            String temp = reverse.reverse().toString();
            ans += dfs(s, temp);
        }

        if(ans > 0){
            return 1;
        }
        else {
            return 0;
        }
    }
}