백준 12904번 A와 B

문제

백준 12904번 A와 B 문제 링크

풀이 방법

되게 간단한 문제라서 이게 왜 골드5지? 싶었다. 그런데 함정이 있었다. 바로 시간복잡도다.
S -> T로 갈 때 두가지 경우가 있고 입력 조건에 따라서 S가 1이고 T가 1000일 경우 최대 2^1000의 시간복잡도를 가진다. 그래서 이렇게 풀면 당연히 틀린다.

그럼 어떻게 풀어야할까?

처음에는 S -> T로 가는 과정 중 중간 종료 조건을 생성해야겠다는 생각을 했다. 그런데 S -> T 과정에서 중간에 유망도를 판단하기는 어려웠다.

그래서 좀 더 고민하다가 결국 생각해냈다.

T -> S로 가는 역발상

T -> S로 가는 과정을 구현하면 된다. 얼핏보면 이것도 2^1000의 시간복잡도 아니야? 라고 할 수 있지만 T -> S로 간다고 생각하면 두가지 경우 중 하나의 경우만 일어난다.

1. T의 끝자리가 A인 경우 : T의 끝자리에서 A를 뺀다.

2. T의 끝자리가 B인 경우 : T의 끝자리에서 B를 뺀 후 문자열을 뒤집는다.

T의 끝자리는 A또는 B 이므로 최대 시간복잡도는 1000이다.

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    //12904번
	public static void main(String[] args) throws Exception {
        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Stack<String> stack = new Stack<>();
        String from = br.readLine();
        String to = br.readLine();
        int fromLength = from.length();
        int result = 0;
        
        stack.push(to);
        
        while(true) {
        	String now = stack.pop();
        	if(now.equals(from)) {
        		result = 1;
        		break;
        	}
        	else if(now.length()>fromLength) {
        		if(now.charAt(now.length()-1) == 'A') {
        			stack.push(now.substring(0, now.length()-1));
        		}
        		//리버스
        		else {
        			stack.push(reverse(now.substring(0, now.length()-1)));
        		}
        	}else if(stack.size() ==0) break;
        }
        bw.write(result+"\n");
        bw.flush();
        
    }
	static String reverse(String s) {
		String newS ="";
		for(int i=s.length()-1; i>=0; i--) {
			newS += s.charAt(i);
		}
		return newS;
	}

}