[백준 BOJ/Gold V] 12904번 : A와 B

 

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

12904번: A와 B

 

문제

- 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임

- 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능
  1) 문자열의 뒤에 A를 추가한다.
  2) 문자열을 뒤집고 뒤에 B를 추가한다.

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

 

처음에는 S에서 T로 만드는 여러가지 경우의 수를 생각했다

생각할수록 뻗어나갈 수 있는 경우의 수가 다양해서 아예 반대로 생각해보기로 했다 역으로 적용해서 지워가면서 T에서 S를 만들 수 있느냐를 따져보기!! 그러니까 문제가 간단해졌다

 

- 문자열의 뒤에 A 추가 → T의 끝에 A가 있다면 제거

- 문자열을 뒤집고 뒤에 B를 추가 → T의 끝에 B가 있다면 제거하고 문자열 뒤집기

 

그렇게 T의 끝을 지우거나 뒤집거나 하면서 S의 길이와 같아질때까지 반복하고, 최종적으로 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();
        int result = 0;

//        System.out.println(T.charAt(T.length()-1));
//        T = T.substring(0,T.length()-1);
//        System.out.println(T);

        while (T.length() > S.length()) { // S와 T 길이가 같아지면 종료
            int n = T.length()-1; // T의 마지막 문자 위치

            if(T.charAt(n) == 'A') {
                T = T.substring(0, n); // 맨 뒤에서 A 제거
            } else { // T.charAt(n) == 'B"
                T = T.substring(0, n); // 맨 뒤에서 B 제거
                StringBuffer sb = new StringBuffer(T);
                T = sb.reverse().toString(); // 뒤집기
            }
        }

        if (S.equals(T)) result = 1;
        System.out.println(result);

    }
}

 

 

많은 문제를 풀어본건 아니지만,, 앞에서부터 접근할 때 많이 복잡하다면 반대로 뒤에서부터 접근하면 간단해지는 문제들이 꽤 있는거같다😎