설명
수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
•
문자열의 뒤에 A를 추가한다.
•
문자열을 뒤집고 뒤에 B를 추가한다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)
출력
S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.
예시 입력
예시 출력
B
ABBA
JavaScript
복사
1
JavaScript
복사
풀이 과정
처음에는 단순히 DFS로 접근하려고 했습니다.
즉, 문자열 + “A”와 문자열.reverse() + “B” 를 하며 T를 찾을 수 있는지 확인했습니다.
public static void dfs(String input) {
if (input.length() > target.length()) {
return;
}
if (input.equals(target)) {
System.out.println(1);
System.exit(0);
}
StringBuilder sb = new StringBuilder(input);
dfs(sb.append("A").toString());
dfs(sb.reverse().toString() + "B");
}
Java
복사
하지만 이는 시간 초과를 불러일으켰습니다. 무수히 많은 경우의 수가 생길 수 있기 때문입니다.
이번 문제는 하향식으로 접근해야 합니다. 즉, target → 시작 input 으로 변환되어야 합니다.
생각해봅시다. 문제에서는 두 가지 연산이 가능합니다.
•
문자열 뒤에 “A”를 추가한다.
•
문자열을 뒤집고 “B”를 추가한다.
다시 말하면, target의 문자열이 “A”로 끝났다면, target은 target.substring(0, target.length()-1)로 대체될 수 있고
target의 문자열이 “B”로 끝났다면 “target은 target.substring(0, target.length()-1) 한 뒤 reverse()로 대체될 수 있습니다.
최종 코드
package baekjoon.string;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class _12904 {
static String input;
static String target;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
input = br.readLine();
target = br.readLine();
System.out.println(isAvaliable(input, target) ? 1 : 0);
}
public static boolean isAvaliable(String start, String end) {
while (end.length() > start.length()) {
if (end.endsWith("A")) {
end = end.substring(0, end.length() - 1);
} else if (end.endsWith("B")) {
end = new StringBuilder(end.substring(0, end.length() - 1)).reverse().toString();
} else {
return false;
}
}
return end.equals(start);
}
}
JavaScript
복사
