[백준 / 자바] 12904 A와 B

Romy·2023년 11월 10일

백준 코딩테스트

📌 문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다.

(1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1

B
ABBA

예제 출력 1

예제 입력 2

AB
ABB

예제 출력 2

📌 풀이

import java.io.*;
import java.util.*;

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

        while (S.length() < T.length()) {
            StringBuilder sb = new StringBuilder();
            if (T.endsWith("A")) {
                T = T.substring(0, T.length() - 1);
            } else if (T.endsWith("B")) {
                T = T.substring(0, T.length() - 1);
                T = sb.append(T).reverse().toString();
            }
        }
        if(S.equals(T)) System.out.println(1);
        else System.out.println(0);
    }
}

📌 기록

처음 생각한 방법과 코드

문제 그대로 앞에서부터 차근 해주려고 했습니다. 사용자가 해야하는 행위는 단 2가지 뿐이라, 2가지의 행위를 해주면 되겠지 생각했는데 시간 초과가 났습니다. 아직도 이렇게 하면 시간초과가 되는구나 하고 감이 안 잡히는 것 같아서 조금 걱정입니다.

import java.io.*;
import java.util.*;

public class Main {
    public static String T;
    public static int result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder S = new StringBuilder(br.readLine());
        T = br.readLine();
        make(S);
        System.out.println(result);

    }
    public static void make(StringBuilder sb) {
        //System.out.println(sb);
        if(sb.toString().equals(T)) {
            result = 1;
        }
        if(sb.length() >= T.length()) {
            return;
        }
        StringBuilder s1 = new StringBuilder(sb);
        StringBuilder s2 = new StringBuilder(sb);

        make(s1.append("A"));
        make(s2.reverse().append("B"));
    }
}

생각의 발상

출발지에서 도착지로 가는 길을 순차적으로 찾는 방법이 하나가 있다면, 도착지에서 출발지로 다시 돌아가는 방법이 또 존재합니다. 해당 문제는 후자 방법으로 접근해야 했습니다. 조금 다시 생각해보면, “자, (초기)상태가 있는데 (완료)상태가 있어. 그리고 가는 방법은 두가지야 ! 이 상태가 될까? 안 될까 ?” 하면, 이미 완료 상태를 알려줬기 때문에, 완료상태에서 초기 상태로 세팅하는 것이 더 빠르다는걸 새로 인지했습니다.