[백준] 12904번 : A와 B - JAVA [자바]

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

---

그리디 알고리즘 문제이다.

왜 그리디 알고리즘 인지는 백준 고수님께서 정리해놓으신게 있다.

-> 이게 왜 그리디인가요?

문제를 쉽게 이해하는 방법이 있다.

S -> T 라고 생각하지 말고 T -> S 라고 생각하는 것이다.

그러면 문제의 조건을 다르게 봐보자.

S 문자열의 뒤에 A를 추가한다.
S 문자열을 뒤집고 뒤에 B를 추가한다.

-> T 문자열의 뒤에 A를 제거한다.
   T 문자열의 뒤에 B를 제거하고 문자열을 뒤집는다.

즉, T의 문자열을 뒤에서 부터 보면서 A 와 B 일때의 행동을 다르게 하며 S와 문자열의 길이가 같아졌을 경우 T 와 S 가 같은지 확인하면 된다.

1. T 의 문자열을 뒤에서 부터 탐색한다.
2. A 일 경우, A 를 제거한다.
3. B 일 경우, B 를 제거하고 문자열을 뒤집는다.
4. S 문자열과 길이가 같아질 때까지 반복한다.
5. S 문자열과 T 문자열의 길이가 같아졌을 때 둘이 같은지 확인하여 정답을 출력한다.

---

public class bj12904 {

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

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

        // 문자열의 뒤에 A를 추가한다.
        // 문자열을 뒤집고 뒤에 B를 추가한다.


        // 문자열의 뒤에 A를 제거한다.
        // 문자열을 뒤집고 뒤에 B를 제거한다.
        // T -> S
        StringBuilder s = new StringBuilder(S);
        StringBuilder t = new StringBuilder(T);
        for (int i = t.length() - 1; i > -1; i--) {
            // S와 문자열의 길이가 같아질 때까지 반복
            if (i == S.length()-1) {
                break;
            }
            // 맨 뒤의 문자열이 B일 경우 B를 제거하고 문자열을 뒤집는다.
            if (t.charAt(i) == 'B') {
                t.deleteCharAt(i);
                t.reverse();
            }
            // 맨 뒤의 문자열이 A일 경우 제거한다.
            else {
                t.deleteCharAt(i);
            }
        }

        if (s.compareTo(t) == 0) {
            System.out.println(1);
        } else System.out.println(0);

        br.close();
    }
}