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

 

12919번: A와 B 2

 

풀이

S와 T의 길이가 같아질 때까지 두 연산 중 하나를 수행해보고 같은 값이 되는 경우의 수가 있는지 확인한다.

브루트포스 문제로 dfs 형태로 구현하였다.

 

주의할 점.

S의 길이를 늘리는 방식으로 하면 시간 초과가 발생한다.

T의 길이를 S만큼 줄이는 방식으로 수행해야 한다.

 

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();

        int answer = search(s, t) ? 1 : 0;
        System.out.println(answer);
    }

    private static boolean search(String s, String t) {
        if (s.length() == t.length()) {
            return s.equals(t);
        }

        if (t.charAt(t.length() - 1) == 'A') {
            boolean isAble = search(s, t.substring(0, t.length() - 1));

            if (isAble) {
                return true;
            }
        }

        if (t.charAt(0) == 'B') {
            return search(s, new StringBuilder(t).reverse().substring(0, t.length() - 1));
        }
        return false;
    }

    // 시간 초과 나는 코드
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String S = scanner.nextLine();
//        String T = scanner.nextLine();
//
//        boolean isAble = search(S, T);
//
//        appendA(S);
//        appendBAndReverse(S);
//
//        int answer = isAble ? 1 : 0;
//        System.out.println(answer);
//    }
//
//    private static String appendA(String word) {
//        return word + "A";
//    }
//
//    private static String appendBAndReverse(String word) {
//        return new StringBuilder(word)
//            .append("B")
//            .reverse()
//            .toString();
//    }
//
//    private static boolean search(String S, String T) {
//        if (S.length() == T.length()) {
//            return S.equals(T);
//        }
//
//        return search(appendA(S), T) || search(appendBAndReverse(S), T);
//    }
}