[백준 12904] A와 B - JAVA

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다.
대표적인 예로

• AB (Abdominal의 약자)
• BAA (양의 울음 소리)
• AA (용암의 종류)
• ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다.
두 문자열 $S$와 $T$가 주어졌을 때, $S$를 $T$로 바꾸는 게임이다.

문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

주어진 조건을 이용해서 $S$를 $T$로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 $S$가 둘째 줄에 $T$가 주어진다.

• $1\ ≤\ S의\ 길이\ ≤\ 999$
• $2\ ≤\ T의\ 길이\ ≤\ 1000$
• $S의\ 길이\ <\ T의\ 길이$

출력

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

---

접근 방법

처음 단순하게 생각했을 때는 브루트 포스로 $S$부터 시작해서 길이가 $T$가 될 때까지
모든 경우의 수를 탐색하는 것이 가장 단순하다고 생각했습니다.
하지만 $T$의 최대 길이 $T_L$를 생각했을 때
시간 복잡도는 $O(2^{T_L-1}) = O(2^{999})$가 된다고 생각했기 때문에
말도 안되는 방법이라고 생각했습니다.

그렇다면 모든 경우를 탐색하는 것이 아니라
역추적 방법과 유사하게 문자열 $T$를 지워나간다면 문제를 해결할 수 있을 것 같았습니다.

그리고 문제에서 주어진 두 가지 연산은
항상 맨 뒤쪽에 문자열을 추가하는 방식이기 때문에 가능하다고 생각했습니다.

그래서 문자열이 정방향인지 역방향인지 판별하는 isReverse라는 boolean 변수를 선언해
정방향일 때는 end 인덱스를 감소시키고
역방향일 때는 start 인덱스를 증가시키는 방법을 사용했고
이 문자열의 길이가 $L$과 동일해질 때 문자열이 같은지 판별하는 재귀 메서드를 구현해 문제를 해결했습니다.

---

초기 코드

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

public class Main {
    static String S;
    static int L;
    static char[] word;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        L = S.length();
        word = br.readLine().toCharArray();

        System.out.println(greedy(0, word.length - 1, false));
    }

    private static String greedy(int start, int end, boolean isReverse) {
        if (Math.abs(end - start) + 1 == L) {
            StringBuilder tmp = new StringBuilder();
            String result;

            if (isReverse) tmp.append(new String(word, end, L)).reverse();
            else tmp.append(new String(word, start, L));

            result = tmp.toString();

            return S.equals(result) ? "1" : "0";
        }

        if (word[end] == 'A') {
            if (isReverse) return greedy(start, end + 1, true);
            else return greedy(start, end - 1, false);
        }
        else {
            if (isReverse) return greedy(end + 1, start, !isReverse);
            else return greedy(end - 1, start, !isReverse);
        }
    }
}

우선 로직은 깔끔히 구현됐지만 두 가지 부분이 아쉬웠습니다.

• 길이가 정해져 있는 거면 재귀를 사용할 필요 없이
  $while$문으로 구현 가능할 것이고 더 효율적일 것입니다.
• 위의 로직에서는 start와 end 인덱스의 역할에 너무 중점을 두어서 역방향일 때에는
  start 인덱스가 end 인덱스보다 큰 경우가 존재합니다.
  • 단순하게 isReverse에 따라 start 증가 또는 end 감소로 단순 구현했으면 더 직관적인 코드가 됐을 것입니다.

이 두 가지 생각을 기반으로 코드를 개선했습니다.

개선된 코드

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

public class Main {
    static String S;
    static int L;
    static char[] word;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        L = S.length();
        word = br.readLine().toCharArray();

        System.out.println(greedy());
    }

    private static String greedy() {
        int N = word.length - L;
        int start = 0;
        int end = word.length - 1;
        boolean isReverse = false;

        while (N --> 0) {
            char lastChar;

            if (isReverse) {
                lastChar = word[start];
            } else {
                lastChar = word[end];
            }

            if (lastChar == 'A') {
                if (isReverse) {
                    start++;
                } else {
                    end--;
                }
            } else {
                if (isReverse) {
                    start++;
                } else {
                    end--;
                }
                isReverse = !isReverse;
            }
        }

        StringBuilder tmp = new StringBuilder();
        String result;

        if (isReverse) {
            tmp.append(new String(word, start, L)).reverse();
        } else {
            tmp.append(new String(word, start, L));
        }

        result = tmp.toString();

        return S.equals(result) ? "1" : "0";
    }
}

재귀 방식 코드

개선된 while 방식 코드

코드는 단순화됐고 효율 또한 시간적으로나 공간적으로나 개선된 모습을 볼 수 있습니다.