백준 [자바 java] 12919 : A와 B 2

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

이 문제는 보자마자 bfs를 이용해서 풀어야겠다! 라고 생각했다.

그래서 생각한대로 풀었는데 시간초과가 났다.. 

알고보니까 나는 S를 T로 만들어가는 과정에서 BFS를 사용했는데, T를 S로 바꾸는 과정에서 BFS를 사용해야 효율적이다.

왜냐하면 S를 T로 만들어가는 과정은 모든 경우의 수를 다 탐색하는데 , T를 S로 바꾸는 과정은 A가 뒤에 있을 때에는 A를 빼고, B가 앞에 있을때에는 B를 빼고 순서를 뒤바꾸는 과정만 거쳐도 정답을 도출할 수 있다.

 

앞으로 이런 문제가 나오면 탑다운 방식으로 풀것인지, 바텀업 방식으로 풀것인지 생각을 해야할 것 같다.

 

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

public class Main {

  public static String change(String k){
    char[] arr = k.toCharArray();
    char[] ans = new char[arr.length];

    for(int i = 0;i<ans.length;i++){
      ans[i] = arr[arr.length-i-1];
    }

    return String.valueOf(ans);
  }

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

    //System.out.println(ans.substring(0,1));

    Queue<String> q = new LinkedList<>();
    q.offer(ans);

    while(q.isEmpty() != true && ori.length() <= q.peek().length()){
      ans = q.poll();
      if(ans.equals(ori)){
        System.out.println(1);
        return;
      }
      if(ans.substring(0,1).equals("B")){
        q.offer(change(ans.substring(1,ans.length())));
      }
      if(ans.substring(ans.length()-1,ans.length()).equals("A")){
        q.offer(ans.substring(0,ans.length()-1));
      }
    }

    System.out.println(0);
  }
}

 

전체 코드는 이러하다

substring에는 대문자가 없다는 것에 유의하자..