[백준] 12919 A와 B 2 - Java

문제

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

 

---

문제 개요

주어진 문자열 S와 T가 있을 때, 주어진 조건을 바탕으로 S를 T로 변환할 수 있는지 알아내는 것이 목표

1. 문자열의 뒤에 A를 추가
2. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는 것이다.

접근 방법

백트래킹을 이용해서 옳바른지 아닌지를 판단

s -> t 순서로 백트래킹을 진행할 경우 시간초과 발생

 

역방향 진행시 장점

1. 효율성: 역으로 진행하면 목표 문자열 T에서 불가능한 경우를 더 빨리 걸러낼 수 있다.
2. 단순화: 문자열을 줄이는 과정이기 때문에 조건을 간단하게 확인할 수 있다.

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

public class Main {
    static String s;
    static String t;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        t = br.readLine();

        isPossible(t);
        System.out.println(answer);
    }


    public static void isPossible(String current) {
        if (current.equals(s)) {
            answer = 1;
            return;
        }
        if (current.length() <= s.length()) {
            return;
        }

        if (current.charAt(current.length() - 1) == 'A') {
            isPossible(current.substring(0, current.length() - 1));
        }

        if (current.charAt(0) == 'B') {
            isPossible(new StringBuilder(current.substring(1)).reverse().toString());
        }
    }
}