[백준] 12919. A와B 2 (Java)

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

12919번: A와 B 2

 

💡 이 문제의 키포인트는 S를 T로 바꿀 수 있는가의 로직이 아니라 T를 S로 바꿀 수 있는지 확인해야 시간초과가 나지 않는다.

💡시간 초과 난 풀이는 S를 가지고 알파벳 “A” 와 “B”를 추가해가며 dfs로 풀었다.

📍Java 문자열 자르기 - substring()

String str = "Hello";

str.substring(1); // ello

str.substring(1,4); // ell : 4번째 문자열 포함 XXXXX 

• substring(startIdx, endIdx) 인 경우 마지막 인덱스는 포함하지 않는다 !!!!!!!

 

✅ 정답 풀이

package algo;

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

public class Main_bj_12919_A와B2 {

    static String S,T;
    static int result;
    static StringBuilder sb;

    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(result);
    }

    private static void dfs(String temp) {

        if(temp.length() == S.length()) {

            if(temp.equals(S)) {
                result = 1;
            }

            return;
        }

// 첫번째 문자가 B라면 첫번째 문자 이후부터 자르고 문자열 뒤집기
        if(temp.charAt(0) == 'B') {
            sb = new StringBuilder(temp.substring(1)).reverse();
            dfs(sb.toString());
        }

// 마지막 문자가 A라면 첫번째 문자부터 마지막 문자 바로 이전까지 자른다.
        if(temp.charAt(temp.length()-1) == 'A') {
            String s = temp.substring(0,temp.length()-1);
            dfs(s);
        }

    }
}

❌ 틀린 풀이

package algo;

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

public class Main_bj_12919_A와B2 {

    static String S,T;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        S = br.readLine();
        T = br.readLine();

        dfs(S);

        System.out.println(result);
    }

    private static void dfs(String temp) {

        if(temp.length() == T.length()) {
            if(temp.equals(T)) {
                result = 1;
            }
            return;
        }

        String s = temp + "A";
//        System.out.print(s+"  ");
        dfs(s);

        String s2 = "B";
        for(int i=temp.length()-1;i>=0;i--) {
            s2 += temp.charAt(i)+"";
        }
//        System.out.print(s2+"\n");
        dfs(s2);
    }
}