문제

아이디어

S -> T로 백트래킹을 진행한다면 최대 2^999번의 연산이 필요하다.
하지만 T -> S로 역산한다면 O(1)의 시간복잡도 안에 풀이가 가능하다.

1. T의 마지막 문자를 제거한다.
2. 제거한 문자가 B라면 T를 뒤집는다.
3. S와 T의 길이가 다르다면 1번으로 이동한다.
4. S와 T가 일치한다면 1, 다르다면 0을 출력한다.

소스코드

import java.io.*;

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

        StringBuilder start = new StringBuilder(br.readLine());
        StringBuilder end = new StringBuilder(br.readLine());

        while (start.length() != end.length()) {
            if (end.charAt(end.length() - 1) == 'A') {
                end = new StringBuilder(end.substring(0, end.length() - 1));
            } else {
                end = new StringBuilder(end.substring(0, end.length() - 1));
                end.reverse();
            }
        }

        if (end.toString().equals(start.toString())) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

채점결과