백준 12904번 A와 B JAVA

링크텍스트

설명

S로 T를 만들 생각하면 안된다.

왜 정방향(S → T)이 어려운가
정방향으로 하면:
매 단계마다 경우의 수가 2개
길이는 계속 늘어남
DFS/BFS 하면 2ⁿ

발상 전환: 역방향(T → S)

정방향 연산을 거꾸로 뒤집어 보자.

뒤의 A 제거,뒤의 B 제거 후 뒤집기

항상 “끝 문자”만 보면 된다
시간복잡도: O(M²), 공간복잡도: O(M)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {

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

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

        StringBuilder sb = new StringBuilder(T);

        while(sb.length()>S.length()){
            char last = sb.charAt(sb.length()-1);

            if(last=='A'){
                sb.deleteCharAt(sb.length()-1);
            }else{
                sb.deleteCharAt(sb.length()-1);
                sb.reverse();
            }
        }

        if(sb.toString().equals(S)){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }
}