[백준] 12919번 : A와 B 2 - JAVA [자바]

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

문자열, 브루트포스 문제이다.

[백준] 12904번 : A와 B - JAVA [자바] 와 비슷하지만 다른 문제이다.

이 문제 또한 S -> T 로 하려면 두가지 연산을 고려하여 골라야 하지만 T -> S 라고 바꿔서 생각하면 1. T 문자열이 A로 시작하는지 2. T 문자열이 B로 끝나는지에 대해서보고 각 조건에 맞는 연산을 해주면 된다.

고려할 조건은 두 가지이다.

1. T 문자열의 맨 뒤가 A 일 경우 A 를 제거한다
2. T 문자열의 맨 앞이 B일 경우 맨 앞의 B를 제거하고 문자열을 뒤집는다

dfs 알고리즘을 이용해서 반복하며, 업데이트되는 T의 길이가 S와 같아졌을 때 둘을 비교하여 같으면 1을 출력하도록 하였다.

public class bj12904 {

    public static String S, T;
    public static int answer = 0;

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

        S = br.readLine();
        T = br.readLine();

        dfs(T);

        System.out.println(answer);

        br.close();
    }

    public static void dfs(String t) {
        // 1. T 문자열의 맨뒤가 A 일 경우 A 를 제거
        // 2. T 문자열의 맨앞이 B일 경우 문자열을 뒤집고 맨 뒤의 B를 제거
        int lenT = t.length();
        // S와 문자열의 길이가 같아질 때까지 반복
        if (lenT == S.length()) {
            if (t.equals(S)) {
                answer = 1;
            }
            return;
        }
        // 1. T 문자열의 맨뒤가 A 일 경우 A 를 제거
        if (t.endsWith("A")) {
            dfs(t.substring(0, lenT - 1));
        }
        // 2. T 문자열의 맨앞이 B일 경우 문자열을 뒤집고 맨 뒤의 B를 제거
        if (t.startsWith("B")) {
            dfs(new StringBuilder(t.substring(1)).reverse().toString());
        }
    }
}