[Java] 백준 12919번: A와 B 2

[문제 바로 가기] - A와 B 2

💡 접근 방식

예전에 풀었던 풀이가 언뜻 기억나서 이거 DFS다!! 하고

1. S를 넣어서 A와 B를 추가하고 문자열 뒤집는걸 for문으로 해서 돌렸다.

2. 1번에서 시간초과가 나자 for문이 문제인가 싶어 StringBuffer로 뒤집는 방법을 찾아 수정했다.

   StringBuffer로 문자열 뒤집기

	StringBuffer sb = new StringBuffer(str);
	String newStr = sb.reverse().toString();    

3. 2번에서 또 시간초과가 나서 결국 예전에 풀었던 풀이를 참고했는데 DFS에 T를 넣어 풀이해야 시간초과가 나지 않는 문제였다.
   T를 넣으면 A로 끝나는지, B로 시작하는지 골라 해당할 때만 DFS를 타고 들어가지만, S를 먼저 넣으면 두 가지 연산을 무조건 수행하기 때문이다.

웃긴 점은 3달 전에도 1~3번의 과정을 똑같이 겪었다는 것 ㅋㅋ ㅜ 나 발전하고 있는거겠지?

풀이

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

public class Main {
	static String S, T;
	static int answer = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S = br.readLine();
		T = br.readLine();
		
		dfs(T);
		
		System.out.println(answer);
	}
	
	public static void dfs(String t) {
		if (t.length() == 0) return;
		if (t.equals(S)) {
			answer = 1;
			return;
		}
		
		
		if (t.charAt(t.length() - 1) == 'A') dfs(t.substring(0, t.length() - 1));
		if (t.charAt(0) == 'B') {
			StringBuffer sb = new StringBuffer(t.substring(1));
			dfs(sb.reverse().toString());
		}
	}
}