문제 탐색하기
입력 자료 정리
- 입력값은 두줄의 문자열이다
첫번째는 바꾸기전 초기 문자열이고, 두번째는 바꾼 후 문자열이다
해결방법 추론
- 이 문제를 해결하기 위해서는 아이디어가 필요하다
- 정방향은 바꾸기전 -> 바꾼 후 문자열로 늘려나가는 방법이고,
역방향은 바꾼 후 -> 바꾸기전 문자열로 줄여나가는 방법이다 - 처음에는 정방향을 선택하여 문제를 해결하였다.
하지만 이 방법은 시간초과를 발생시켰다 - 두번째로 생각한 방법은 역방향이다.
이 방법을 선택했을 때는 조건을 사용할 수 있어서 문제없이 해결할 수 있었다. - 3~4번에 대해서는 아래에서 자세히 다룰 것이다.
- 역방향 방법을 선택했으므로 이제 문자를 줄여나가는 방법을 고안해야한다
- 주어진 조건대로 문자를 줄여나가는 방법을 생각하였다
- 만약 맨 뒤의 값이 A인 경우, 맨 뒤의 값을 지운 문자열을 백트래킹으로 넘겨준다
- 만약 맨 앞의 값이 B인 경우, 맨 앞의 값을 지운 뒤 뒤집어서 문자열을 백트래킹으로 넘겨준다
- t가 s보다 길이가 작거나 둘이 같은 문자열일 때 종료시키며,
만약 두 문자열이 같다면 정답을 위한 작업을 진행하도록 하자 - 백트래킹 방법을 선택했을 때, 그리고 역방향으로 문자열을 줄이는 방법을 선택했을 때,
정방향으로 선택한 것보다 가짓수를 더 줄일 수 있어 시간초과없이 문제를 해결할 수 있을 것이다.
시간복잡도 계산
- 정방향으로 했을 때, 시간복잡도는 O(2^(|T|-|S|))으로 계산하였다.
T와 S를 생각했을 때, 49정도 나올 것이고 2^49면 시간제한을 넘어버린다.
여기서 역방향으로 한다면 조건에 따라 가짓수가 더 줄어들 것이고,
문제를 제출했을 때 시간제한을 넘지 않고 해결하는 것을 확인할 수 있다.
사실 시간복잡도 계산이 정확하지는 않고, 직접 틀려가면서 시간초과를 줄여야하기때문에
썩 괜찮은 문제로 보이지는 않는다...
코드 설계하기
입력값 상태관리
- 입력값은 문자열로 관리해준다. s, t 문자열 변수로 관리한다
- 정답 출력을 위한 ans 변수는 초기값으로 0을 선언한다.
백트래킹 결과 아무런 변화를 주지 못했을 때, 0을 출력하기 위함이다
구현 코드 설계
- 바로 백트래킹을 돌려준다. s의 길이가 t의 길이보다 클때 종료,
둘이 같을 때 ans를 1로 초기화하고 종료한다. - 만약 t의 끝 문자가 A라면 뒤의 값을 지우고 넘긴다.
이때 StringBuilder를 사용하여 불변 문자열을 손쉽게 다룰 수 있도록 바꿔준다 - 첫 문자가 B인 경우 동일하게 StringBuilder를 사용하여 첫 문자를 지우고 뒤집는다
- 각 조건 후에는 StringBuilder의 값을 t 인수로 넘겨준다
출력값 설계
- 완성한 ans를 출력하면 정답이 된다.
과거 해결 실패 분석
시간초과 분석
- 정방향으로 갔을 때, 시간 초과가 발생함을 간과했기 떄문에 틀렸다
- 정방향에서는 최대 2^49정도의 연산이 발생할 수 있음을 계산했다면,
정방향 백트래킹을 선택하지 않았을 것이다
역방향 구현 실패
- 정방향으로 했을 때는 무조건 두가지 선택지에 대한 경우를 모두 고려해야한다
- 하지만 역방향은 이미 만들어진 문자열을 분석해서 뺼지를 결정하므로
조건을 넣고 구분할 수 있다. - 이 점을 파악하지 못해서 구현에 실패한 것이 두번째 실패 이유이다
- 또한 이 방식이 시간초과가 과연 발생하지 않을 까?에 대한 불신도 한몫했다
해결방안
- 내가 선택한 방법에 대한 시간초과를 꼭 먼저 고려하자.
그리고 틀렸다면, 다른 방법에 대해서 먼저 고민을 하자 - 역방향 구현 실패는, 두가지를 키워야한다.
먼저 문제를 잘 이해하고, 이것을 잘 풀어내는 역량
두번째는 구현 역량이다.
이 방법을 위해서는 꾸준히 장문의 구현 문제를 풀면서 키우는 방법밖에 없다
현재 코드트리에서 삼성 구현 문제를 풀고 있는데, 이 방법을 통해 역량을 키워나갈 것이다
정답 코드
import java.io.*;
import java.util.*;
public class Main {
static int ans = 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));
String s = br.readLine();
String t = br.readLine();
backtracking(s, t);
bw.write(ans+"");
br.close();
bw.close();
}
private static void backtracking(String s, String t) {
if(s.length() > t.length()){
return;
}
if(s.equals(t)){
ans = 1;
return;
}
if(t.charAt(t.length()-1) == 'A'){
StringBuilder sb = new StringBuilder(t);
sb.deleteCharAt(t.length()-1);
backtracking(s, sb.toString());
}
if(t.charAt(0) == 'B'){
StringBuilder sb = new StringBuilder(t);
sb.deleteCharAt(0);
sb.reverse();
backtracking(s, sb.toString());
}
}
}
문제 링크
Software Developer