[BaekJoon] 12904 A와 B (Java)

1.  문제 링크

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

2.  문제

요약

• A와 B로만 이루어진 두 문자열 S, T가 주어졌을 때, S를 T로 바꾸는데 아래의 두 가지 연산만 이용할 수 있습니다.
  • 문자열의 뒤에 A를 추가합니다.
  • 문자열을 뒤집고 뒤에 B를 추가합니다.
• 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 문제입니다.
• 입력: 첫 번째 줄에 문자열의 길이가 1보다 크거나 같고 999보다 작거나 같은 문자열 S가 주어지고 두 번째 줄에 문자열의 길이가 2보다 크거나 같고 1000보다 작거나 같은 문자열 T가 주어집니다.
  • 문자열 S의 길이는 문자열 T의 길이보다 작습니다.
• 출력: 첫 번째 줄에 S를 T로 바꿀 수 있다면 1을, 없다면 0을 출력합니다.

3.  소스코드

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

public class Main {
	static String s, t;
	public String reverse(String str) {
		return new StringBuilder(str).reverse().toString();
	}
	
	public int canChange() {
		while(t.length() > s.length()) {
			if(t.charAt(t.length() - 1) == 'A') {
				t = t.substring(0, t.length() - 1);
			} else {
				t = t.substring(0, t.length() - 1);
				t = reverse(t);
			}
		}
		if(t.equals(s)) {
			return 1;
		} else {
			return 0;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		s = br.readLine();
		t = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.canChange() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제에서는 S를 T로 바꿀 수 있는지 여부를 확인해야하는데, 이를 S에서 T를 만드는 것이 아닌 T에서 S가 만들어지는지를 생각해보겠습니다.
• 문자열 T의 마지막 문자가 A인 경우, 위 조건에서 첫 번째 조건을 1번, 두 번째 조건을 2번이라고 한다면 2번 조건은 진행될 수 없습니다.
• S에서 2번 조건을 진행한다면, 문자열을 뒤집고 마지막에 B를 추가하기 때문에 마지막 문자열이 B가 될 수 밖에 없으므로 T의 마지막 문자가 A인 경우 이를 만들 수 없게 됩니다.
• 문자열 T의 마지막 문자가 B인 경우, 1번 조건은 진행될 수 없습니다.
• S에서 1번 조건을 진행한다면, 문자열 마지막에 A를 추가하기 때문에 마지막 문자열이 A가 될 수 밖에 없으므로 T의 마지막 문자가 B인 경우 이를 만들 수 없게 됩니다.
• 위 2가지 경우를 이용하여 T에서 S를 만들어가보고 만들 수 있다면 1을, 없다면 0을 출력합니다.

1. 주어진 문자열 S, T를 각각 변수 s, t에 넣습니다.
2. 문자열 T의 길이가 문자열 S의 길이보다 클 때까지 반복문을 돌면서 T를 S로 만들 수 있는지를 확인합니다.
   1. 만약 문자열 T의 마지막 문자가 A라면 T에서 마지막 문자를 제거합니다.
   2. 만약 문자열 T의 마지막 문자가 B라면 T에서 마지막 문자를 제거하고 문자열 T를 거꾸로 뒤집습니다.
3. 2번 반복문이 끝난 후에, 문자열 T와 S가 같다면 S에서 T를 만들 수 있다는 뜻이므로 1을 출력하고 그렇지 않다면 만들 수 없다는 뜻이므로 0을 출력합니다.