[BOJ] 12919 A와 B 2 - JAVA

1. 문제

12919번: A와 B 2

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

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

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

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

---

2. 풀이

1.  S,T를 모두 입력받아서 char 배열로 만든다.

2.  T에서 S를 만들 수 있는지 check함수로 확인한다. 만약 true라면 1을 출력하고, false라면 0을 출력한다.

3.  check함수는 a부터 b까지 way 방향으로 탐색한다. way가 true라면 오->왼, false라면 왼->오 방향이다.

3-1.  오->왼 방향이고 b값이 'A'라면 끝값인 b를 빼고 check함수를 부른다.

3-2.  오->왼 방향이고 a값이 'B'라면 첫번째 값인 a를 빼고 check함수를 부른다. 이 때, 방향은 뒤집어서 불러야 한다.

3-3.  왼->오 방향이고 a값이 'A'라면 끝값인 a를 빼고 check함수를 부른다.

3-4.  왼->오 방향이고 b값이 'B'라면 첫번째 값인 b를 빼고 check함수를 부른다. 방향도 뒤집는다.

3-5.  3-1~3-4까지 true값이 나온 적 있다면 리턴하고 끝낸다.

3-6.  b-a==S길이라면 방향에 따라 순서대로 탐색한 뒤, 동일할 때 true를 반환한다.

import java.io.*;

public class BOJ_12919_A와B2 {
   static char[] S,T;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      S = in.readLine().toCharArray();
      T = in.readLine().toCharArray();

      if(check(0,T.length-1,true)) System.out.println(1);
      else System.out.println(0);
   }

   public static boolean check(int a, int b, boolean way){
      boolean ans = false;
      if(b-a == S.length-1){
         for(int i=0;i<=b-a;i++){
            if(way && S[i] != T[a+i]) return false;
            else if(!way && S[i] != T[b-i]) return false;
         }
         return true;
      }

      if(way){
         if(T[b]=='A') ans = check(a,b-1,way);
         if(!ans && T[a]=='B') ans = check(a+1,b,!way);
      }else{
         if(T[a]=='A') ans = check(a+1,b,way);
         if(!ans && T[b]=='B') ans = check(a,b-1, !way);
      }

      return ans;
   }
}

---

3. 결과