[BOJ] 12919번 - A와 B 2 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

입력으로 주어지는 문자열의 길이도 크지 않고 연산도 간단해서 아래와 같이 코드를 작성했다.

public static int solve(String s, String t) {
    if(s.length() == t.length()) {
        if(s.equals(t)) return 1;
        return 0;
    }
    String s1 = s + "A";
    String s2 = new StringBuffer(s + "B").reverse().toString();
    if(solve(s1, t) == 1 || solve(s2, t) == 1) return 1;
    return 0;
}

 

문자열 s에 연산을 해나아가며 문자열 t와 같아지는지 확인했다.

하지만 결과는 시간초과가 떴다.

위와 같이 풀이를 할 경우 s에서 t까지 찾아가는 경우의 수가 기하급수적으로 늘어날 수 있다.

그림에서와 같이 s의 길이가 1이고 t의 길이가 4일 경우 s의 길이가 4가 될 8가지 방법이 존재한다.

내가 푼 방식은 8번 모두 탐색한 후 결과를 반환할 수 있을 것이다.

 

즉, n (t의 길이 - s의 길이) 이라고 할 때 탐색하는 경우의 수는 2^n 으로 기하급수적으로 경우의 수가 증가한다.

시간초과가 나는 이유도 모든 경우를 확인해서 발생한 것이다.

모든 경우를 확인하지 않고도 판별할 수 있는 방법을 생각해야한다.

 

s에 연산을 해나가면서 t를 만든다는 것은 t를 역연산을 적용해서 s를 만든다는 것과 같다.

즉, 반대로 문자열 t에 역으로 연산을 해서 s를 만드는 방법을 사용하는 것이다.

• 문자열의 뒤에 A를 추가한다. → 맨뒤의 문자가 A일 경우 제거한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. → 맨앞의 문자가 B일 경우 이를 제거하고 뒤집는다.

예전에 비슷한 문제를 풀었는데 똑같이 틀려서 오답노트를 작성한다 생각하고 글을 써보았다.ㅎㅎ

---

🍀 풀이 🍀

package Baekjoon;

import java.io.*;

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

        String s = br.readLine();
        String t = br.readLine();
        System.out.println(solve(s, t));
    }

    public static int solve(String s, String t) {
        if(s.length() == t.length()) {
            if(s.equals(t))
                return 1;
            return 0;
        }

        int answer = 0;
        if(t.charAt(t.length()-1) == 'A') {
            answer += solve(s, t.substring(0, t.length()-1));
        }
        if(t.charAt(0) == 'B') {
            answer += solve(s, new StringBuffer(t.substring(1)).reverse().toString());
        }
        return answer > 0 ? 1 : 0;
    }
}