[Baekjoon] 12904번: A와 B - Java

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

12904번: A와 B

문제 설명

문자열 S와 T가 주어졌을 때, 주어진 규칙으로 S를 T로 만들 수 있는지 여부를 계산하는 문제이다.

풀이 방법

이 문제는 발상의 전환이 필요하다. S에서 T로 만들려면 모든 경우의 수를 따져야 한다. 하지만 T에서 S로 만드는 것은 'A와 'B' 중 한 가지만 고려하면 된다.

T를 S로 만드는 방법은 다음과 같다.

• A로 끝나면 마지막 문자를 제거한다.
• B로 끝나면 마지막 문자를 제거하고 문자열을 뒤집는다.

핵심 코드는 다음과 같다.

while (T.length() > S.length()) {
    if (T.endsWith("A")) {
        T = T.substring(0, T.length() - 1);
    } else if (T.endsWith("B")) {
        T = T.substring(0, T.length() - 1);
        T = new StringBuilder(T).reverse().toString();
    }
}

만약 S를 T로 만들게 되면 고려할 사항이 엄청나게 늘어난다. 문자를 하나 추가할 때마다 생기는 모든 경우의 수를 따져야 하기 때문이다. 아마 재귀를 통해 할 수는 있겠지만 알고리즘 자체도 복잡해질 뿐더러 효율 또한 좋지 않다.

전체 코드는 다음과 같다.

package baekjoon.string;

import java.io.*;

public class BOJ12904 {
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String S = br.readLine();
            String T = br.readLine();

            while (T.length() > S.length()) {
                if (T.endsWith("A")) {
                    T = T.substring(0, T.length() - 1);
                } else if (T.endsWith("B")) {
                    T = T.substring(0, T.length() - 1);
                    T = new StringBuilder(T).reverse().toString();
                }
            }

            System.out.print(T.equals(S) ? 1 : 0);
        }
    }
}