전공공부
[BOJ_12919] A와 B 2 본문
설명
재귀함수를 사용하는 문제였으며 처음에는 일일이 S -> T로 만드는 방법을 썼지만 12%에서 시간 초과가 났고 생각을 비틀어서 T -> S로 변경하여 소거법으로 진행하였다.
그러면, 문제 조건중 '문자열 뒤에 B를 추가하고 뒤집는다.' 가 있으니 B가 맨 앞에 있는 경우는 B의 경우로 들어온 것임을 유추 할 수 있어서 오히려 조건의 반대로 맨 앞의 B를 빼고 다시 뒤집는 것을 B의 조건으로 만들고 재귀함수 돌리고 A의 경우에는 '문자열 뒤에 A를 추가한다' 가 있으니 맨 뒤에 A를 빼고 재귀를 돌리는 형식으로 S를 만들어 나갔다.
그런데, 이 소거법을 진행하면서 간과한 것이... T = T.subString(1); 이런식으로 재귀를 돌아가는 T의 조건을 바꾸어 버렸다. 이런식으로 진행해버리면 다음 if문에 들어가는 경우에는 T의 조건이 바뀐 채로 재귀가 돌아가니 정상적인 케이스가 될 수가 없는데 당시에는 이걸 깨닫지 못하고 다른 블로그가 틀린 코드를 올린 줄 알았다.
재귀를 돌아갈때는 당연하지만 원상태 그대로의 것이 새로 변경되면서 돌아가야 하므로 이런 포인트를 주의 하는게 좋겠다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ_12919 {
static boolean check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
String T = br.readLine();
canTransform(S,T);
if (check) {
System.out.println(1);
} else {
System.out.println(0);
}
}
private static void canTransform(String S, String T) {
if (S.length() == T.length()) {
if (S.equals(T)) {
check = true;
}
return;
}
if(S.length() > T.length()){
return;
}
if (T.charAt(0) == 'B') {
canTransform(S, reverseString(T.substring(1)));
}
if (T.charAt(T.length() - 1) == 'A') {
canTransform(S,T.substring(0, T.length() - 1));
}
}
private static String reverseString(String str) {
StringBuilder sb = new StringBuilder(str);
return sb.reverse().toString();
}
}
12919번: A와 B 2
수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈
www.acmicpc.net
'Study > Problem Solving' 카테고리의 다른 글
[BOJ_2581] 소수 (0) | 2023.09.19 |
---|---|
[BOJ_17615] 볼 모으기 (0) | 2023.09.10 |
[BOJ_14940] 쉬운 최단거리 (0) | 2023.09.05 |
[BOJ_1205] 등수 구하기 (0) | 2023.09.05 |
슬라이딩 윈도우 (0) | 2023.09.03 |