[BOJ] 12904. A와 B

[작성일]

• 2022-03-02

[분류]

• 그리디
  
  
  

[문제링크]

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

[요구사항]

• 문자열 S를 T로 만들 수 있는지 구하라.
  
  
  

[풀이]

그리디 문제이다.
S를 T로 만들기 위해서는 문제에 주어진 두 가지 방법을 시도해나가면서 나아가야하는데, 이렇게 될 경우 경우의 수가 너무 많아지고 규칙이 따로 없다.
그래서 이미 만들어져 있는 T는 무조건 A 또는 B가 추가되면서 만들어진 결과이기 때문에 역으로 하나씩 글자를 줄여나가면서 S길이만큼으로 만들고 동일한지 확인하는 식으로 구현하면 무난히 구현할 수 있다.

[코드]

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

public class Main {
    static StringBuilder S, T;

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

        // S를 T로 바꾸려면 A를 추가하거나 뒤집고 B를 붙여가는 식으로 나아가야하는데 경우가 많아서 어렵다.
        // T는 이미 규칙에 따라 완성된 문자열이기 때문에 반대로 줄여나가보자.
        while (S.length() < T.length()) {
            boolean check = false;
            if (T.charAt(T.length() - 1) == 'B') {
                check = true;
            }
            T.deleteCharAt(T.length() - 1);
            if (check) T.reverse();
        }

        if (new String(S).equals(new String(T))) System.out.println(1);
        else System.out.println(0);
    }
}