[Gold V] A와 B - 12904 (JAVA)

문제 요약

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

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

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

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

---

문제 분석

미로찾기를 생각하면 편하다.

미로의 시작점에서 도착점까지 가는 과정보다, 도착점에서 시작점으로 가는 게 더 수월할 거다.

주어진 두 개의 연산을 반대로 생각하고 문제를 풀어보자.

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        /*
            문제에서 알려준 두가지 연산은 다음과 같다.
            - 문자열의 뒤에 A를 추가한다.
            - 문자열을 뒤집고 뒤에 B를 추가한다.
            이는 S를 T로 만드는 과정에서의 연산이다.
            하지만 이를 반대로 생각해보면,
            - 문자열의 뒤에 A를 지우기
            - 뒤에 B를 지우고 문자열을 뒤집기
            둘 다 문자열 뒤의 한글자를 지운다는 공통점이 생긴다.
            다음 특징을 활용해서 문제를 접근해보자.
         */
        int result = 0;
        while(T.length() > S.length()){
            char lastChar = T.charAt(T.length()-1);
            // 공통적으로 지워준다.
            T = T.substring(0, T.length()-1);
            // B일 경우만 T를 뒤집어준다.
            if(lastChar == 'B'){
                T = reverse(T);
            }
        }
        if(T.equals(S)){
            result = 1;
        }
            System.out.println(result);
    }

    private static String reverse(String before){
        String after = "";
        char[] array = before.toCharArray();
        for(int i = 0; i < array.length; i++){
            after+=array[array.length-1-i];
        }
        return after;
    }
}

---

정리

새로 배운 내용

가끔은 문제를 반대로 접근해보자.

개선할 점

보자마자 완탐을 생각한 나 자신을 개선!

더 찾아볼만한 사항

문자열 역순으로 변경하는 거 stringbuilder에서 가능했던 거 같은데 벌써 까먹었다.

---