[백준][12904][Java] A와 B

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

12904번: A와 B

문제풀이

문제를 딱 보자마자 완전 탐색을 하면 되겠다 생각했지만 최악의 경우 S가 1이고 T가 1000일 경우 BFS를 1000번 실행하기 때문에 스택오버플로우가 발생한다.

 

다르게 생각한 방법으론 Queue를 이용해서 A와 B를 더하면서 체크하는 방법이었는데 이 방법 또한 최악의 경우 2^1000 만큼의 값을 Queue에 담기 때문에 메모리 초과가 났다.

 

그래서 생각한 방법은 S를 기준으로 잡지 않고 T를 기준으로 잡아 마지막 문자가 A 인경우는 그냥 지워주고

B 인 경우는 문자열을 뒤집어 주었다. 문자를 하나씩 줄이면서 S와 길이가 같아졌을때 S와 T를 비교해서 맞다면 S로 T를 만들 수 있다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String S = br.readLine();
		String T = br.readLine();
		
		int result = 0;
		int size = T.length();
		
		for(int i=0; i<size; i++) {
			char c = T.charAt(T.length()-1);
			
			T = T.substring(0,T.length()-1);
			
            // B인 경우 뒤집어 준다.
			if(c == 'B') {
				StringBuilder sb = new StringBuilder(T);
				T = sb.reverse().toString();
			}
			
            // S와 길이가 같다면 S와 T 비교
			if(S.length() == T.length()) {
				if(S.equals(T)) result =1;
				break;
			}
		}
        
		System.out.println(result);
	}
}