[Baekjoon] 12919_A와 B 2

Gold V

문제(출처: https://www.acmicpc.net/problem/12919)

---

<A와 B 2>

 

문제 풀이

 

구현하는 방법에서 S에서 T로 변환할까 T에서 S로 변환할까를 처음에 고민했다.

 

그러다 S에서 T는 시간초과가 날까 싶어서 T에서 S로 변환하는 방법을 택하였다. 그 후 S에서 T로 변환하는 코드도 구현해 보았다. 역시나 시간초과였다!

 

T에서 S로 변환하는 방법은

1) 문자열 뒤에 A 추가(원래 조건) -> 문자열 뒤에 A가 있으면 A제거 후 넣기

2) 문자열의 뒤에 B를 추가하고 문자열 뒤집기(원래 조건) -> 문자열 맨 앞에 B가 있으면 맨 앞 문자열 빼고 뒤집기

를 사용했다.

 

 

 - my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _12919_ { // A와 B 2

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

		Queue<String> queue = new LinkedList<>();
		queue.add(T);

		boolean flag = false;
		while (!queue.isEmpty()) {
			String temp = queue.poll();

			if (temp.length() - 1 < S.length())
				continue;

			// 문자열 뒤에 A 제거
			if (temp.charAt(temp.length() - 1) == 'A') {
				String a = temp.substring(0, temp.length() - 1);
				if (a.equals(S)) {
					flag = true;
					break;
				}
				queue.add(a);
			}

			// 맨 앞 문자열 B 제거 후 뒤집기
			if (temp.charAt(0) == 'B') {
				String a = "";
				for (int i = temp.length() - 1; i > 0; i--) {
					a += temp.charAt(i);
				}
				if (a.equals(S)) {
					flag = true;
					break;
				}
				queue.add(a);
			}
		}
		if (flag)
			System.out.println(1);
		else
			System.out.println(0);
	}
}

 

S를 T로 바꿀 수 있냐를 물어보는 문제이지만 문제 해결은 T를 S로 바꿀 수 있냐로 해결하였다.

 

T를 S로 바꾸는 경우에는 맨 뒤가 A인지, 맨 앞이 B인지를 통해 가지치기를 할 수 있기 때문이다.

 

만약 S를 T로 바꾸는 코드를 구현했더라면 맨 뒤에 A를 붙이고, 맨 뒤에 B를 붙이고 뒤집기를 해도 T 문자열의 길이만큼 완성해야 S를 T로 만들 수 있는지 알 수 있기 때문에 시간초과가 발생하는 것이다.

 

• S, T 입력
• queue: 문자열 저장
• flag: T -> S로 바꿀 수 있는지 check
• queue가 빌 때까지 반복
  • 문자 하나를 뺀 문자열의 길이가 S의 길이보다 작으면 S를 만들 수 없기 때문에 continue
  • 문자열 맨 뒤가 'A'라면 제거 -> 그 문자열이 S라면 break; S가 아니라면 queue에 추가
  • 문자열 맨 앞이 'B'라면 제거 및 뒤집기 -> 그 문자열이 S라면 break; S가 아니라면 queue에 추가

---

생각🤔

 

예전에 비슷한 문제를 풀었던 기억이 나서 쉽게 해결할 수 있었다.

 

하지만 다른 방법도 도전해보고 싶어 도전해봤지만 역시나 시간 초과였다.

 

 

---