[백준][12904번: A와 B]

문제

문제링크

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

문제풀이

처음에 dfs로 S->T로 변환하는 방법으로 선택했다.
하지만 시간초과가 나서 반대로 T->S를 가는 방법을 선택하니 문제가 풀렸다.
T->S 방법
1. T의 맨 끝 글자를 확인
2. 맨 끝 글자가 A일 경우 -> A를 지운다.
3. 맨 끝 글자가 B일 경우 -> B를 지우고 T를 뒤집는다.

처음 코드(시간초과)

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

public class Main {
    static boolean check = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        change(S,T);
        if(check){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }
    static void change(String S, String T){
        if(S.length() == T.length()){
            if(S.equals(T)){
                check = true;
            }
            return;
        }
        change(S + 'A', T);
        change(reverse(S) + 'B', T);
    }
    static String reverse(String s){
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
}

정답 코드

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

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();
        System.out.println(change(S,T));
    }
    static int change(String S, String T){
        while(S.length()!=T.length()){
            if(T.charAt(T.length()-1) == 'A'){
                T = T.substring(0,T.length()-1);
            }else{
                T = T.substring(0,T.length()-1);
                T = reverse(T);
            }
        }
        if(S.equals(T)){
            return 1;
        }else{
            return 0;
        }
    }
    static String reverse(String s){
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
}

느낀점

항상 문제 설명과 조건들을 잘 읽어야지 하는데 잘 읽지 않아서 시간초과 나거나 틀린다......
코딩테스트를 볼 때 테스트케이스만 주어지는 곳이 많다.
만약에 위 문제가 나왔을 경우 테스트케이스가 통과되서 그냥 제출 했을 것이다. 그렇게 되면 시간초과로 문제를 틀리게 된다...
위와 같은 상황이 발생하지 않도록 문제 설명과 조건들을 잘 보도록 노력해야겠다.