문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

문자열의 뒤에 A를 추가한다.
문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

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

접근법1

S를 T로 바꿀 수 있는지 직접 조건에 맞게 수행해서 확인하는 방법을 채택했다.
그러나 시간초과가 났다.

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

public class Main {

    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokens;
    String S, T;
    int answer;

    void Input() throws IOException {
        S = input.readLine();
        T = input.readLine();
    }

    void recursive(String crnt) {
        if (crnt.equals(T)) {
            System.out.println(1);
            System.exit(0);
        }
        if (crnt.length() > T.length()) {
            return;
        }
        recursive(crnt + "A");
        StringBuffer sb = new StringBuffer(crnt + "B");
        String reverse = sb.reverse().toString();
        recursive(reverse);
    }

    void Solve() throws IOException {
        Input();
        recursive(S);
        System.out.println(0);
    }

    public static void main(String[] args) throws Exception {
        new Main().Solve();

    }

}

접근법 2

그래서 반대로 T에서 S를 만드는 방식을 채택하였다.
시간초과가 나지않고 빠른 속도로 통과하였다.

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

public class Main {

    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokens;
    String S, T;
    int answer;

    void Input() throws IOException {
        S = input.readLine();
        T = input.readLine();
    }

    void makeS(String crnt) {
        if (crnt.equals(S)) {
            answer = 1;
            return;
        }

        if (crnt.length() > S.length()) {
            if (crnt.charAt(crnt.length() - 1) == 'A') {
                makeS(crnt.substring(0, crnt.length() - 1)); // 'A'를 제거
            }
            if (crnt.charAt(0) == 'B') {
                String tmp = crnt.substring(1); // 'B'를 제거하고 뒤집기
                StringBuilder sb = new StringBuilder(tmp);
                tmp = sb.reverse().toString();
                makeS(tmp);
            }
        }
    }

    void Solve() throws IOException {
        Input();
        makeS(T);
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().Solve();

    }

}

왜 S에서 T로 가는 방법은 시간초과가 났을까?

gpt에게 물어봤다.

S에서 T로 가는 방식이 시간초과가 나는 이유는, 가능한 모든 경우를 탐색해야 하기 때문입니다. 이 방식에서는 재귀적으로 각 단계에서 두 가지 선택을 할 수 있는데:

1. 문자열에 'A'를 추가한다.
2. 문자열에 'B'를 추가하고 뒤집는다.

이 두 가지 선택을 모든 단계에서 고려해야 하기 때문에, 가능한 문자열의 조합 수가 기하급수적으로 증가하게 됩니다. 그 결과 탐색할 경우의 수가 너무 많아져서 시간 초과가 발생합니다.

왜 기하급수적으로 증가하는가?

• 매번 두 가지 선택을 할 수 있기 때문에, 한 번의 탐색이 끝나면 그 다음 단계에서 또다시 두 가지 선택을 해야 합니다.
• 만약 최대 k 단계(즉, T의 길이에서 S의 길이를 뺀 값)만큼의 변환을 해야 한다면, 최악의 경우 2^k개의 경우의 수를 탐색해야 합니다.
  • 예를 들어, S에서 T로 가는 과정이 10단계 정도 걸린다면 2^10 = 1024가지 경우를 고려해야 하고, 이 값은 단계가 늘어날수록 기하급수적으로 증가합니다.

구체적인 예시

• S = A이고 T = BAAA인 경우, S에서 T로 가는 과정에서 가능성 있는 모든 변환은 다음과 같이 됩니다:

  1. 첫 번째 선택: 'A'에 'A'를 추가하거나, 'B'를 추가하고 뒤집기
  2. 두 번째 선택: 각 선택에 대해 다시 'A'를 추가하거나 'B'를 추가하고 뒤집기

  이런 식으로 매번 두 가지 선택을 해야 하므로 가능한 경우의 수가 2^k에 비례하게 됩니다.

반면, T에서 S로 가는 방식은 왜 더 효율적인가?

T에서 S로 가는 방식이 효율적인 이유는, 문자열의 길이를 매번 확실히 줄여가며 탐색할 수 있기 때문입니다. T에서 S로 가는 과정에서는 다음 두 가지 변환만 가능합니다:

1. 마지막 문자가 'A'일 경우 'A'를 제거한다.
2. 마지막 문자가 'B'일 경우 'B'를 제거하고 문자열을 뒤집는다.

이 방법은 매번 문자열의 길이를 확실하게 1씩 줄이기 때문에, 탐색하는 경우의 수가 줄어듭니다. T에서 S로 변환할 때의 경우의 수는 최대 T의 길이 - S의 길이만큼의 변환 과정만 고려하면 되므로, 탐색해야 할 경우의 수가 선형적으로 줄어듭니다.

결론

• S에서 T로 가는 방식은 매번 두 가지 선택을 하며 탐색하기 때문에, 기하급수적으로 경우의 수가 증가하여 시간초과가 발생합니다.
• 반면, T에서 S로 가는 방식은 문자열의 길이를 매번 줄이며 탐색하므로 효율적입니다.

실험

재귀함수가 몇번 호출되었는지 확인하기 위해서 재귀함수에서 전역변수 cnt를 계속해서 1씩 증가시켰다.

입력

S = A
T = BABABABABA

결과

1. S>T의 경우

    void makeT(String crnt) {
        cnt++;
        if (crnt.equals(T)) {
            System.out.println(1);
            System.out.println(cnt);
            System.exit(0);
        }
        if (crnt.length() < T.length()) {
            recursive(crnt + "A");
            StringBuffer sb = new StringBuffer(crnt + "B");
            String reverse = sb.reverse().toString();
            recursive(reverse);
        }
    }

2. T>S의 경우

    void makeS(String crnt) {
        cnt++;
        if (crnt.equals(S)) {
            answer = 1;
            return;
        }

        if (crnt.length() > S.length()) {
            if (crnt.charAt(crnt.length() - 1) == 'A') {
                makeS(crnt.substring(0, crnt.length() - 1)); // 'A'를 제거
            }
            if (crnt.charAt(0) == 'B') {
                String tmp = crnt.substring(1); // 'B'를 제거하고 뒤집기
                StringBuilder sb = new StringBuilder(tmp);
                tmp = sb.reverse().toString();
                makeS(tmp);
            }
        }
    }