[백준] A와 B 2

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

12919번: A와 B 2

 

완탐 문제

 

문자열 연산의 종류 2가지

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

 

이때, S를 T로 바꿀 수 있다는 말은  T를 거꾸로 S로도 바꿀 수 있냐는 의미

 

T를 S로 바꿀때

 

1) T 맨뒤가 A인 경우

    - A를 뺀다

    - 뒤집고 맨뒤가 B인 경우 B를 뺀다 (B가 아닌 경우는 고려X)

 

2) T 맨뒤가 B인 경우

   -  뒤집고 맨뒤가 B인 경우 B를 뺀다 (B가 아닌 경우는 고려X)

 

코드

package algorithm.baekjoon.bj12919;

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

public class Main {
    private static boolean isSame = false;

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

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

        changeString(S, T, T.length() - 1);
        System.out.println(isSame ? 1 : 0);
    }

    private static void changeString(String s, String t, int lastIdx) {
        if (isSame) return;
        if (s.length() == t.length()) {
            if (s.equals(t)) isSame = true;
            return;
        }

        //A를 뺀다
        if (t.charAt(lastIdx) == 'A') {
            changeString(s, t.substring(0, lastIdx), lastIdx - 1);
        }
        //문자열 뒤집고 B를 뺀다 (B 없으면 불가능)
        if (new StringBuilder(t).reverse().toString().charAt(lastIdx) == 'B') {
            changeString(s, new StringBuilder(t)
                    .reverse()
                    .substring(0, lastIdx), lastIdx - 1);
        }
    }
}

 

기존 문제대로 S에 조건마다 모든 값을 대입하는 것보다 T를 거꾸로 삭제시키는 방식이 더 빠름

(거꾸로 조건이 성립하지 않는 경우는 제외시키기 때문)

 

만약 기존 문제대로 2가지 조건을 모두 대입할 경우,

S의 길이 최소 1

T의 길이 최대 50

 

최악의 경우 2^50의 시간복잡도가 발생