백준 [자바 java] 12904 : A와 B

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

12904번: A와 B

 

처음에는 dfs로 풀었는데 시간초과가 났다. 그래서 더 효율적인 방법을 찾다가 완성된 문자열에서 처음 문자열로 돌아가는 방법을 쓰게 되었다. 

문자열의 제일 끝이 A이면 이전에 기존 문자열 끝에 A를 썼다는 의미이므로 A를 뺴고 그대로 두면 되고, B이면 B를 빼고 문자를 뒤집으면 된다. 

이를 반복하다가 문자가 아예 사라지면 break를 통해 나오고 안된다는 결론을 내면 된다.

 

import java.io.*;
import java.util.*;



public class Main {

    static String BB(String k){
        char[] arr = k.toCharArray();
        char[] arr2 = new char[arr.length-1];

        for(int i = 0;i<arr.length-1;i++){
            arr2[i] = arr[arr.length -2 -i];
        }

        return new String(arr2);
    }

    static String AA(String k){
        char[] arr = k.toCharArray();
        char[] arr2 = new char[arr.length-1];

        for(int i = 0;i<arr.length-1;i++){
            arr2[i] = arr[i];
        }

        return new String(arr2);
    }

    public static void main(String[] args) throws IOException{

        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        String fir = br.readLine();
        String sec = br.readLine();

        //String Stack 만들고 이를 이용해서 풀기
        Stack<String> s = new Stack<>();



        s.push(sec);

        while(s.isEmpty() != true){
            String now = s.pop();
            //System.out.println(now);

            char[] arr = now.toCharArray();
            if(arr.length == 0) break;

            if(arr[arr.length-1] == 'A'){
                String k= AA(now);
                s.push(k);
            }

            if(arr[arr.length-1] == 'B'){
                String k= BB(now);
                s.push(k);
            }

            //System.out.println(now);

            if(now.equals(fir)){
                System.out.println(1);
                System.exit(0);
            }


        }

        System.out.println(0);

    }
}