[백준/JAVA] 12919번: A와 B 2

📖 문제

https://www.acmicpc.net/problem/12919

 

 

 

💡  풀이 방식

• 재귀

S에서 T를 만드는 재귀를 수행하는 게 아니고,

T에서 문자열을 지우면서 S를 만드는 재귀를 수행하는 것이다.

[재귀 함수]
- (종료 조건) 첫 번째 문자열과 두 번째 문자열의 길이가 같고, 두 문자열이 같다면, 1을 출력한다. (같지 않다면 0을 출력한다.)
- 두 번째 문자열의 마지막 글자가 A인 경우> 마지막 글자를 하나 뺀 값을 재귀함수의 인자로 갖고 가 재귀를 수행한다.
- 두 번째 문자열의 맨 앞 글자가 B인 경우 > 맨 앞 글자를 하나 빼고, 뒤집은 값을 인자로 가져가 재귀를 수행한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static String S, T;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        S = br.readLine();
        T = br.readLine();
        
        System.out.println(solve(S, T));
    }
    
    private static int solve(String s, String t) {
        if(s.length() == t.length()) {
            if(s.equals(t))
                return 1;
            return 0;
        }
        
        int ans = 0;
        
        // 마지막 글자가 A인 경우
        if(t.charAt(t.length() - 1) == 'A') {
            ans += solve(s, t.substring(0, t.length() - 1));    // 마지막 글자 하나 빼기
        }
        
        // 맨 앞 글자가 B인 경우
        if(t.charAt(0) == 'B') {
            StringBuilder s1 = new StringBuilder(t.substring(1));   // 맨 앞 글자 하나 빼기
            String newStr = s1.reverse().toString();                // 뒤집기
            ans += solve(s, newStr);
        }
        
        return ans > 0 ? 1 : 0;
    }
}

 

 

➕ 다른 풀이 방식

charAt() 메소드 안 사용하시고, startsWith()과 endsWith() 메소드를 사용하신 풀이

[백준] 12919번 : A와 B 2 - JAVA [자바]

 

---

💦 어려웠던 점

- 맨 처음에는 S에서 T를 만들도록 모든 경우의 수를 돌리는 재귀를 실행했었고... 15%에서 시간 초과로 틀렸었다~~~ (아무래도 만드는 것보다 줄이는 편이 더 효율적일테니..)

- 그 다음에 T를 S로 만드는 재귀를 수행하면 되겠다! 해서 맨 뒤부터 문자를 없애면서 문제를 풀 생각을 했는데 그게 아니었다,, 

 

 

🧐 새로 알게 된 내용

dfs 함수의 리턴값을 정답에 누적해 저장하는 것,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 12919 [자바] java A와 B 2