(BOJ 12919) A 및 B 2(JAVA)

문제

수빈은 A와 B로만 이루어진 영어 단어가 있다는 사실에 놀랐다. AB(Abdominal), BAA(Crying Sheep), AA(Art Lava), ABBA(Swedish pop group) 등이 대표적이다.

이 사실에 놀란 수빈은 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어지면 이 게임은 S를 T로 변환합니다. 문자열을 변경할 때 두 가지 작업만 가능합니다.

• 문자열 끝에 A를 추가합니다.
• 문자열 끝에 B를 추가하고 문자열을 뒤집습니다.

주어진 조건에서 S가 T가 될 수 있는지 알아보는 프로그램을 작성하십시오.

기입

S는 첫 번째 줄에, T는 두 번째 줄에 제공됩니다. (1 ≤ S 길이 ≤ 49, 2 ≤ T 길이 ≤ 50, S 길이 < T 길이)

누르다

S를 T로 변환할 수 있으면 1을 반환하고 그렇지 않으면 0을 반환합니다.

구현: 임의의 캐릭터에 대해 특정 작업을 수행할 때 티이 포인트를 사용하게 됩니다 반대로 T를 한 문자씩 줄이는 연산입니다.를 수행하고, T가 될 수 있는 문자열을 연속적으로 찾으면서 S가 일치하는지 여부를 판단하였다.

t를 기준으로 역동작다음과 같다.

• (1) 문자열 ‘A’의 마지막 문자를 삭제합니다.
• (2) 문자열의 첫 번째 문자인 ‘B’를 삭제하고 문자열을 뒤집습니다.

하나) T의 첫 글자가 ‘A’인 경우

• 문자열을 변경할 때 첫 문자가 ‘A’이면 마지막 문자는 ‘A’여야 합니다.
  (‘B’가 오면 마지막에 ‘B’가 나오지 않도록 글자를 뒤집는다)

        // 1 ) 첫 문자가 'A'인 경우
        if (now.charAt(0) == 'A')
        {
            // 'A'로 시작하고 'B'로 끝나는 문자열은 만들 수 없으므로 탐색 종료
            if (now.charAt(now.length() - 1) == 'B')
                return;
            // 가장 뒤에 추가된 'A'를 제외
            back( now.substring(0, now.length()-1) );
        }

2) T의 첫 글자가 ‘B’인 경우(이 경우 경우의 수를 먼저 두 개로 나눕니다)

• T의 마지막 문자는 ‘비‘ 만약에: (2) 계산을 수행하다
• T의 마지막 문자는 ‘ㅏ‘ 만약에: ‘ㅏ’마지막에 추가되며, ‘비’마지막에 추가된다 (하나)그리고 (2) 모든 계산을 합니다.

        else // if(now.charAt(0) =='B') 2) 첫 문자가 'B'인 경우
        {
            // 가장 마지막 문자가 'B'인 경우 앞에서 B를 제거하고 뒤집는다.
            if (now.charAt(now.length() - 1) == 'B') {
                sb = new StringBuilder( now.substring(1, now.length()) );
                back( sb.reverse().toString() );
            }
            else // if (now.length() -1 == 'A')
            {
                sb = new StringBuilder( now.substring(1, now.length()) );

                // 'B'가 마지막에 추가되어 뒤집어졌거나 'A'가 마지막에 추가된 경우
                back( sb.reverse().toString() );
                back( now.substring(0, now.length() - 1) );
            }
        }

제출 결과

소스 코드

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

/**
 * A와 B 2
 */
public class BOJ12919 {

    static String S, T;
    static StringBuilder sb;
    
    static int length;

    static boolean equal = false;
    static void back(String now){

        // 탐색 종료 조건
        if (equal || now.length() <= length) {

            if (now.hashCode() == S.hashCode())
                equal = true;
            return;
        }
        
        // 1 ) 첫 문자가 'A'인 경우
        if (now.charAt(0) == 'A')
        {
            // 'A'로 시작하고 'B'로 끝나는 문자열은 만들 수 없으므로 탐색 종료
            if (now.charAt(now.length() - 1) == 'B')
                return;
            // 가장 뒤에 추가된 'A'를 제외
            back( now.substring(0, now.length()-1) );
        }
        else // if(now.charAt(0) =='B') 2) 첫 문자가 'B'인 경우
        {
            // 가장 마지막 문자가 'B'인 경우 앞에서 B를 제거하고 뒤집는다.
            if (now.charAt(now.length() - 1) == 'B') {
                sb = new StringBuilder( now.substring(1, now.length()) );
                back( sb.reverse().toString() );
            }
            else // if (now.length() -1 == 'A')
            {
                sb = new StringBuilder( now.substring(1, now.length()) );

                // 'B'가 마지막에 추가되어 뒤집어졌거나 'A'가 마지막에 추가된 경우
                back( sb.reverse().toString() );
                back( now.substring(0, now.length() - 1) );
            }
        }
    }

    public static void main(String() args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        S = bufferedReader.readLine();
        T = bufferedReader.readLine();
        length = S.length();

        back(T);

        if (equal)
            System.out.println(1);
        else
            System.out.println(0);
    }

}

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