1. 문제 설명
- S와 T 두 문자열이 주어짐.
- 두 문자열은 모두 A, B로만 이루어져 있고, 다음 두 연산을 사용할 수 있음.
- 문자열 뒤에 A를 추가
- 문자열 뒤에 B를 추가하고, 문자열 전체를 뒤집음
- 이 연산을 여러 번 사용해서 문자열 S를 문자열 T로 만들 수 있으면 1, 없으면 0을 출력하는 문제
// [input]
A // S
BABA // T
// [output]
1 // or 02. 스크래치
정방향 (S → T)
- 정방향은 길이를 1씩 늘리는 방법
- 매 단계마다 2개의 선택지가 있음
1) 뒤에 A를 붙이기 or
2) 뒤에 B를 붙이고 뒤집기 - S의 길이가 n, T의 길이가 m이면 총 m-n번 연산을 해야 함 ⇒ 가능한 연산 수 2^(m-n)
- 문자열 뒤집는 연산
- 모든 경우를 만들어 보는 방법(완전 탐색)은 시간/ 메모리적 한계
역방향 (T → S)
- 역방향은 매번 길이를 1씩 줄임
- 역연산의 조건
1) 끝이 A일 때만 마지막 A 제거
2) 시작이 B일 때만 첫 B 제거 후 뒤집기 기능 - 메 단계마다 2가지 경우가 아니라, 조건이 맞을 때만 연산 수행 가능
- 역방향 풀이가 유리한 이유?
- 깊이가 최대 m-n으로 고정됨 (길이가 계속 줄어듦)
- 항상 2가지 경우가 아닌 조건부이므로 분기가 줄어듦
- 중복 문자열은 visited로 차단 가능
- DFS/ BFS로 T를 S 길이까지 줄여서 같아지는지 검사
3. 풀이
주요 로직
역방향으로 문자열(cur)을 한 단계씩 검사
- cur의 마지막 글자가 A라면 (….A)
→ 정방향 연산에서 A를 붙였던 경우이므로 마지막 A를 제거 - cur의 첫 글자가 B라면 (B…..)
→ 정방향 연산에서 뒤에 B를 붙이고 뒤집었던 경우이므로 첫 글자 B를 지우고 뒤집어서 다시 복구 - 길이가 1씩 줄어들으므로 DFS / 백트래킹으로 T를 S 길이까지 줄이며 확인하기
4. 코드
주요 로직
1) 전역 변수: visited
static Set<String> visited = new HashSet<>();
- Set 타입: 같은 값 중복 저장 X → 이미 값이 들어있는지를 O(1)로 빠르게 연산 가능
- DFS를 돌 떄 같은 문자열 상태가 나오면 함수 실행을 막음
- 현재 문자열 cur 상태에서 가능한 연산을 visited에 저장
→ 같은 cur이 나오면 계속 볼 필요 X
2) dfs 탈출조건
- (1) 전역 변수 found가 true인 경우
S와 길이가 같고, 값이 같을 때 - (2)
!visited.add(cur)이 - (3) 길이가 S와 같아질 경우
더 줄이면 길이가 달라져 절대 S가 될 수 없음
public class Main {
static String S,T;
static Set<String> visited = new HashSet<>();
static boolean found = false;
public static void main(String[] args) throws IOException {
// [input]
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
S = br.readLine().trim();
T = br.readLine().trim();
// [logic]
dfs(T);
// [output]
System.out.println(found?1:0);
}
static void dfs(String cur) {
if(found) return;
if (visited.contains(cur)) return;
visited.add(cur);
if(cur.length() == S.length()) {
if(cur.equals(S)) found = true;
return;
}
// 마지막 글자가 A이면
if(cur.charAt(cur.length()-1)=='A') {
dfs(cur.substring(0,cur.length()-1)); // 마지막 글자 A 지우고 다시 탐
}
// 첫 글자가 B이면
if(cur.charAt(0)=='B') {
String trimmed = cur.substring(1); // == substring(1,cur.length())
String next = new StringBuilder(trimmed).reverse().toString();
dfs(next);
}
}
}
5. De-fault
1) visited 배열이 왜 필요한가?
- 길이가 매번 1씩 줄어들면서 서로 다른 경로로 줄여오다가 같은 문자열 상태인 경우가 생김
- visited가 없으면 해당 문자열에서 시작되는 하위 탐색을 똑같이 수행하기 때문에 낭비가 커짐
- 역 연산은 2가지 방법이 가능 (끝이 A일 경우, B로 시작하는 경우)
- 어떤 문자열은 두 조건을 동시에 맞목할 수 있고, 두 연산을 다른 순서로 적용하면서 내려오다 보면 결과가 같은 문자열로 합쳐질 수 있음
- Set 자료 구조 이용
visited는 이미 탐색한 문자열 상태를 저장해두고, 같은 cur가 다시 나오면 재탐색을 막는 가지치기 용도
→ 방문 여부 확인 & 없으면 기록하는 데 평균적으로 빠른 자료구조는 HashSet
e.g. BAA
[1]
BAA -> BA (끝이 A)
BA -> A (B제거 후 뒤집기)
[2]
BAA -> AA (B제거 후 뒤집기)
AA -> A (끝이 A)2) StringBuilder를 사용하는 이유
- String은 immutable이므로 문자열을 뒤집거나 붙이는 작업을 String으로 처리하면 내부적으로 새 문자열이 계속 만들어져 비용이 커질 수 있음
- StringBuilder는 mutable이라서 내부 버퍼에서 문자를 처리하여 reverse() 같은 연산을 효율적으로 수행할 수 있음
이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂
