백준 12904번 A와 B

DFS + 완전탐색 풀이 (시간 초과)

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

public class AandB {
    static String T;
    static Boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        T = br.readLine();
        dfs(S);
        if(!flag){
            System.out.println(0);
        }
    }
    public static void dfs(String str){
        if(str.length()>T.length()){
            return;
        }
        if(str.equals(T)){
            System.out.println(1);
            flag = true;
            System.exit(1);
        }
        for (int i = 0; i < 2; i++) {
            String nstr;
            if(i==0){
                nstr = plusA(str);
            }
            else {
                nstr = turnAndPlusB(str);
            }
            dfs(nstr);
        }
    }

    public static String turnAndPlusB(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = str.length()-1; i >=0 ; i--) {
            sb.append(str.charAt(i));
        }
        sb.append("B");
        return String.valueOf(sb);
    }

    public static String plusA(String str) {
        StringBuilder sb = new StringBuilder();
        sb.append(str).append("A");
        return String.valueOf(sb);
    }
}

DFS + 그리디 풀이(정답)

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

public class AandB {
    static String S;
    static Boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        String T = br.readLine();
        dfs(T);
        if(!flag){
            System.out.println(0);
        }
    }
    public static void dfs(String str){
        if(str.equals(S)){
            System.out.println(1);
            flag = true;
            System.exit(0);
        }
        if(str.length()<=S.length()){
            return;
        }
        String prestr;
        if(str.charAt(str.length()-1)=='A'){
            prestr = minusA(str);
        }
        else if(str.charAt(str.length()-1)=='B'){
            prestr = minusBAndTurn(str);
        }
        else {
            return;
        }
        dfs(prestr);

    }

    public static String minusBAndTurn(String str) {
        StringBuilder temp = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        temp.append(str).delete(str.length()-1,str.length());
        for (int i = temp.length()-1; i >=0; i--) {
            sb.append(temp.charAt(i));
        }
        return String.valueOf(sb);
    }

    public static String minusA(String str) {
        StringBuilder sb = new StringBuilder();
        sb.append(str).delete(str.length()-1,str.length());
        return String.valueOf(sb);
    }
}

문제 조건

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

풀이방법

이 문제는 완전탐색으로 접근하기 쉬운데, 사실 여러 경우의 수가 있는것이 아니라 문제 조건을 보면 다음 탐색이 고정되어 있다.

1. 문자열 T의 마지막 문자가 A일 경우
   2번조건은 불가능하게 된다.
   2번 연산을 했을 경우, 마지막 문자는 B여야 하기 때문이다.

2. 문자열 T의 마지막 문자가 B일 경우
   1번조건은 불가능하게 된다.
   1번 연산을 했을 경우 마지막 문자는 A여야 하기 때문이다.

📢즉 문자열 T의 마지막 문자가 A라면 그 직전의 연산은 반드시 1번 연산, 마지막 문자가 B라면 그 직전의 연산은 반드시 2번 연산이었어야 한다.

완전탐색시 S에서 T가 되는 경우

그리디 탐색시 S에서 T가 되는경우

👉따라서 T에서 마지막 문자열을 확인하며, 거꾸로 탐색하여 S가 되는지를 확인해야 한다.

1. 마지막 문자가 A라면 prestr에 minusA()함수 반환값을 담고, B라면 prestr에 minusBAndTurn()함수 반환값을 담는다.
2. prestr을 dfs에 재귀호출 해준다.
3. minusBAndTurn()와 minusA()는 StringBuilder를 사용하여 문자열을 제거, 뒤집는다.
4. S와 같아지는 순간이 오면 1을 출력하고 flag를 체크하고, 종료한다.
5. T의 문자열 길이가 점점 줄어 S보다 작아졌는데도, flag 체크가 안되어있다면, 0을 출력한다.

후기

처음에 완전탐색으로 풀었다가 시간초과가 발생하였다.
문제 조건에 따라 핵심을 파악할 수 있는지가 중요한 문제였다.
그외 System.exit(0)은 정상종료 System.exit(1)은 비정상 종료로 런타임에러가 발생한다.