문제

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

풀이

처음에 dfs로 모든 경우를 검사하게 만들었다가 시간초과 뜨고 아무리 생각해도 아닌거 같아서 참고했습니다.
천재님의 설명

접근 방법

정답을 만들지 말고, 정답에서 처음 줬던 문자열로 되돌아가는게 핵심입니다.

핵심 원리

첫번째 테스트 케이스인 B, ABBA를 그림으로 나타내봤습니다. 모든 경우의 수를 나타냈습니다.
접근 방법에서 설명드렸던 정답에서 뒤로 돌아가는걸 생각해봅시다.
파란색 노드인 ABBA에선 뒤로 돌아가는 방법은 문제에서 설명한 방법의 역순인 두가지 입니다.

1. A를 맨 뒤에서 제거한다 -> ABB
2. B를 맨 뒤에서 제거한 뒤, 뒤집는다. -> 불가능

그렇습니다. 뒤로 가는 방법은 정해져 있습니다.

따라서 다음과 같은 방식으로 되돌아가면 됩니다.

1. 맨 뒤가 A -> A를 제거한다.
2. 맨 뒤가 B -> B를 제거하고 뒤집는다.

이렇게 돌아가서 주어진 처음 문자열과 길이가 같아졌을 때 비교해서 같다면 1, 아니라면 0을 출력하면 됩니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder source = new StringBuilder(br.readLine());
        StringBuilder target = new StringBuilder(br.readLine());

        while (target.length() != source.length()) {
            if (target.charAt(target.length() - 1) == 'A') {
                deleteA(target);
            } else {
                deleteBAndReverse(target);
            }
        }

        if ((target.toString()).equals(source.toString())) {
            answer = 1;
        }

        System.out.println(answer);

    }
    
    public static void deleteA(StringBuilder str) {
        str.deleteCharAt(str.length() - 1);
    }

    public static void deleteBAndReverse(StringBuilder str) {
        str.deleteCharAt(str.length() - 1);
        str.reverse();
    }
}

마치며

저도 언젠간 코테를 많이 풀다보면 저런 사고를 할 수 있는 날이 오겠죠??

Reference

https://www.acmicpc.net/board/view/83783