[백준] 12919번 - A와 B 2 (java)

Baekjoon 12919 - A와 B 2 (클릭 시 이동)

문제

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

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

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	1837	661	528	36.820%

입력

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

출력

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

풀이

Target 문자열에서 조건의 반대로 적용해가면서 Source 문자열로 만들 수 있는지 확인하면 된다.

Source : A

Target : BABA 의 경우

맨 뒤의 A를 빼볼 수도 있고, 뒤집은 다음 B를 없애 ABA를 만들어 볼 수도 있다.

이러한 모든 방법을 재귀함수를 통해 확인한다.

Source의 길이와 같을 때 재귀문을 종료한다.

최종 소스코드

package BJ_Practice.Gold;

import java.io.*;
import java.util.*;

public class BJ_G5_12919_A와_B2 {
    static String S, T;
    static int Slen;

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

        S = br.readLine();
        T = br.readLine();
        Slen = S.length();


        if (solve(T)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    static boolean solve(String str) {
        if(str.length() == Slen) {            // 길이가 같다면 확인 후 종료
            if(str.equals(S)) return true;
            return false;
        }

        if(str.charAt(str.length()-1) == 'A') {            // 맨 뒤가 A라면 A를 빼고 다시 탐색
            if(solve(str.substring(0, str.length()-1))) {
                return true;
            }
        }

        if(str.charAt(0) == 'B') {        // 맨 앞이 B라면 B를 빼고 뒤집은것만 다시 탐색.
            StringBuilder reverse = new StringBuilder();
            reverse.append(str.substring(1,str.length()));
            if(solve(reverse.reverse().toString())) {
                return true;
            }
        }
        return false;
    }
}