[백준] 12919: A와 B 2 - JAVA

in Algorithm on 문자열

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

풀이

문자열, 브루트포스 문제이다.

A와 B로만 이루어진 단어들이 있는데

첫번째 주어지는 단어(S)로 두번째 단어(T)를 만들 수 있는지 확인하는 문제이다.

문자열을 바꿀 때는 “문자열의 뒤에 A를 추가한다”, “문자열의 뒤에 B를 추가하고 문자열을 뒤집는다” 이 두가지의 연산이 가능하다.

S에서 T를 만드려면 두 가지 연산을 모두 시도해야 하지만

T에서 S를 만들 때는 문자열의 뒤에 A가 있는지, 문자열의 앞에 B가 있는지 확인하여 그 경우에만 연산을 하면 된다.

문자열을 뒤집는 방법으로는 for문을 이용한 방법과 StringBuilder의 reverse를 이용한 방법이 있다.

String reverse = "";
for (int i = len - 1; i > 0; i--) {
    reverse += t.charAt(i);
}

String reverse = new StringBuilder(t).reverse().toString();

위 두가지 방법이 문자열을 뒤집는 방법들이다.

StringBuilder.reverse를 이용한 방법이 더 빨랐다.

메모리: 14280KB

시간: 136ms

언어: Java 11

코드

import java.io.*;

public class Main {
    static String S, T;
    static int ans;

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

        ans = 0;
        makeS(T);

        System.out.println(ans);
    }

    private static void makeS(String t) {
        int len = t.length();

        if (len == S.length()) {
            if (t.equals(S)) {
                ans = 1;
            }
            return;
        }

        if (t.endsWith("A")) {
            makeS(t.substring(0, len - 1));
        }

        if (t.startsWith("B")) {
            makeS(new StringBuilder(t.substring(1)).reverse().toString());
        }
    }
}