[BOJ_12919] A와 B 2

설명

---

재귀함수를 사용하는 문제였으며 처음에는 일일이 S -> T로 만드는 방법을 썼지만 12%에서 시간 초과가 났고 생각을 비틀어서 T -> S로 변경하여 소거법으로 진행하였다. 

 

그러면, 문제 조건중 '문자열 뒤에 B를 추가하고 뒤집는다.' 가 있으니 B가 맨 앞에 있는 경우는 B의 경우로 들어온 것임을 유추 할 수 있어서 오히려 조건의 반대로 맨 앞의 B를 빼고 다시 뒤집는 것을 B의 조건으로 만들고 재귀함수 돌리고 A의 경우에는 '문자열 뒤에 A를 추가한다' 가 있으니 맨 뒤에 A를 빼고 재귀를 돌리는 형식으로 S를 만들어 나갔다.

 

그런데, 이 소거법을 진행하면서 간과한 것이... T = T.subString(1); 이런식으로 재귀를 돌아가는 T의 조건을 바꾸어 버렸다. 이런식으로 진행해버리면 다음 if문에 들어가는 경우에는 T의 조건이 바뀐 채로 재귀가 돌아가니 정상적인 케이스가 될 수가 없는데 당시에는 이걸 깨닫지 못하고 다른 블로그가 틀린 코드를 올린 줄 알았다.

 

재귀를 돌아갈때는 당연하지만 원상태 그대로의 것이 새로 변경되면서 돌아가야 하므로 이런 포인트를 주의 하는게 좋겠다.

코드

---

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

public class BOJ_12919 {
    static boolean check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();

        canTransform(S,T);

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

    private static void canTransform(String S, String T) {

        if (S.length() == T.length()) {
            if (S.equals(T)) {
                check = true;
            }
            return;
        }
        if(S.length() > T.length()){
            return;
        }

        if (T.charAt(0) == 'B') {
            canTransform(S, reverseString(T.substring(1)));
        }

        if (T.charAt(T.length() - 1) == 'A') {
            canTransform(S,T.substring(0, T.length() - 1));
        }


    }
    private static String reverseString(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }

}

 

12919번: A와 B 2