[백준 12904] - A와 B(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/12904

12904번: A와 B

---

[문제풀이] 

 

처음은 문자열 S 를 T 로 바꿀 수 있는지 찾으려고 접근을 해봤습니다. S에서 A를 추가하거나, 뒤집고 B를 추가하는 방식 2가지중 하나를 선택하면 풀지 않을까 생각을 했는데 문제 제한 조건이 T의 길이가 1000보다 작다고 주어졌습니다.

이 방법으로 구현을 하면 2^1000 이기 때문에 당연히 시간초과가 날 것이고..

 

문제를 S -> T 가 아닌 T -> S 로 가면 해결할 수 있다는 것을 알았습니다. 왜냐하면 문제에서 주어진 두 가지 연산만 가능하기 때문에 S의 길이보다 T의 길이가 클때 문자열의 마지막이 A 이면 A를 제거하고 B일때는 제거 후 뒤집으면 됩니다. 그렇게해서 시간복잡도를 O(T) 만큼 줄일 수 있습니다.

 

문자열을 쉽게 뒤집기 위해 StringBuilder를 사용했습니다.

 

---

[소스코드] 

 

 

import java.io.*;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder s = new StringBuilder(br.readLine());
        StringBuilder t = new StringBuilder(br.readLine());

        while (s.length() < t.length()) {
            if (t.charAt(t.length() - 1) == 'A') {
                t.deleteCharAt(t.length() - 1);
            }else if (t.charAt(t.length() - 1) == 'B') {
                t.deleteCharAt(t.length() - 1);
                t.reverse();
            }
        }

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