[백준 알고리즘] 12919번 : A와 B 2 (JAVA) 문제 풀이

문제

수빈이는 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

12919번: A와 B 2

문제 풀이 :

모든 경우의 수를 체크해야 한다 <- 브루트 포스 알고리즘이다.

최근에는 브루트포스 알고리즘을 중점적으로 풀고있는데, 무언가 패턴이 보이기 시작한다.

우선 재귀를 이용해 탈출 조건으로 S와 T의 문자열의 길이가 같으면 탈출하고, S와 T가 같은 문자열일 경우 답을 1로 출력하게 끔 하였다.

또한 T의 마지막 글자가 A일 경우 마지막 글자를 빼고, 첫번째가 B일 경우 B를 빼고 뒤집는다.

그리하여, S와 같다면 답은 1, 아니라면 0을 출력하게끔 코딩하였다.

 

내 코드 :

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

public class Main {

	static String S;
	static String T;
	static int answer = 0;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S = br.readLine();
		T = br.readLine();

		solve(S, T);

		System.out.println(answer);

	}

	private static void solve(String s, String t) {
		if (s.length() == t.length()) {
			if (s.equals(t)) {
				answer = 1;
			}

			return;
		}
		int ans = 0;
		if (t.charAt(0) == 'B') {
			String substring = t.substring(1);
			StringBuilder sb = new StringBuilder(substring);
			String string = sb.reverse().toString();
			solve(s, string);
		}

		if (t.charAt(t.length() - 1) == 'A') {
			solve(s, t.substring(0, t.length() - 1));
		}
		return;

	}

}