[BOJ] 12904 A와 B

A와 B

풀이

• 문자열 S, T가 주어졌을 때, S를 T로 바꾸는데 두 가지 연산만 사용해서 바꿔야 한다.

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

• 처음에는 모든 경우의 수를 고려하는 완탐으로 풀었다. 그랬더니 시간초과.

  🙅‍♀️ 틀린 코드

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String s = br.readLine();
          String t = br.readLine();
          Stack<String> stack = new Stack<>();
          stack.push(s);
          boolean answer = false;
          while(!stack.isEmpty()){
              String now = stack.pop();
              if(now.length()==t.length()){
                  if(now.equals(t)){
                      answer = true;
                  }
              }
              else{
                  StringBuilder sbA = new StringBuilder(now).append('A');
                  StringBuilder sbB = new StringBuilder(now).reverse().append('B');
                  stack.push(sbA.toString());
                  stack.push(sbB.toString());
              }
          }
          System.out.println(answer ? "1":"0");
      }
  }

• 역발상이 중요했다... T가 주어지면, T를 S로 바꾸는 것이다.
  T의 끝에서부터 시작한다. T의 마지막 문자가 A라면, A를 없애고, 마지막 문자가 B라면, B없애고 문자를 뒤집는다.
  T의 끝문자를 확인하기 위해서, String 클래스의 endsWith를 썼다는 점.
  그렇게 T가 S와 길이가 같아질 때 까지 진행하고, 같아진 경우에 equals 함수로 비교하면 끝.

  🙆‍♀️ 정답 코드

    import java.util.*;
    import java.io.*;
    public class Main {
    	public static void main(String[] args) throws Exception {
          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);
          }
      }
  }