백준 12904번 - A와 B

문제

백준 12904번 - A와 B

아이디어

• 현재 상황에 따라 최적의 선택지를 고르는 그리디 알고리즘으로 해결한다.
• T에서 S로 갈 수 있는지 확인한다.
• T의 마지막이 "A"면 마지막 문자를 제거한다.
• T의 마지막이 "B"면 마지막 문자를 제거하고, 뒤집는다.
• S와 T의 길이가 같아질 때까지 반복 후, 두 문자열이 일치하는지에 따라 결과를 출력한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

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

/**
 * <a href = "https://www.acmicpc.net/problem/12904">백준 12904번 - 그리디 : A와 B</a>
 * <br>
 * <a href = "">velog</a>
 * @since 2024-07-12
 */
public class BJ_12904 {
    public static void main(String[] args) throws IOException {

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

        String s = br.readLine();
        String t = br.readLine();

        while (s.length() != t.length()) {
            if (t.endsWith("A")) {
                t = t.substring(0, t.length() - 1);
            } else {
                t = t.substring(0, t.length() - 1);
                t = new StringBuilder(t).reverse().toString();
            }
        }

        System.out.println(s.equals(t) ? 1 : 0);
    }
}