[백준 12904번 / java] A와 B

문제

12904번: A와 B (acmicpc.net)

1. 문자열 S, T가 주어진다.

2. S를 변형하여 T가 될 수 있는지 출력한다.

풀이

S->T 로 변형 가능한지 확인하는 경우 :

조건에 따른 모든 경우를 구해야 판단 가능하므로 2^n번의 연산이 필요하다.

2^10 = 약 1,000 이므로 최악의 경우 2^1000 = 약 1000^100 < 2억

 

T->S 가 될 수 있는지 확인하는 경우:

이 경우는 문자열 T의 끝 문자가 A인 경우 A를 삭제, B인 경우 B를 삭제 후 뒤집는 경우만 연산하면 되므로 총 n번의 연산이 필요하다. 앞선 방법보다 훨씬 적은 시간복잡도로 구할 수 있다.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String A = br.readLine();
        String B = br.readLine();

        int ans = 0;

        while(true){
            char lastAlp = B.charAt(B.length()-1);
            if(lastAlp == 'A'){
                B = B.substring(0, B.length()-1);
            }else if(lastAlp == 'B'){
                B = B.substring(0, B.length()-1);
                StringBuffer sb = new StringBuffer(B);
                B = sb.reverse().toString();
            }

            if(B.equals(A)){
                ans = 1;
                break;
            }

            if(B.length() == 1)
                break;
        }

        bw.write(ans + " ");
        bw.close();

    }
}