A와 B 2(BJ_G5_12919)

1. 문제 링크

 

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

 

---

 

2. 나의 코드

메모리: 14316kb
시간: 108ms
코드 길이: 1107B
시간 복잡도 : O(N^2)
설명
- 완성된 문자열을 가지고 문자를 하나씩 없애가면서 DFS를 사용하였다.
- 만약 문자열의 길이가 짧아지면 멈추는 백트래킹을 사용하였다.

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

public class BJ_12919 {
    static String from, to;
    static int found = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        from = br.readLine();
        to = br.readLine();

        dfs(new StringBuilder(to));
        System.out.println(found);
    }

    public static void dfs(StringBuilder sb) {
        if (found == 1) return; // 이미 찾았다면 더 이상 탐색하지 않음
        if (sb.toString().equals(from)) {
            found = 1;
            return;
        }
        if (sb.length() < from.length()) return;

        if (sb.charAt(0) == 'B') {
            StringBuilder newSb = new StringBuilder(sb);
            newSb.deleteCharAt(0).reverse();
            dfs(newSb);
        }

        if (sb.charAt(sb.length() - 1) == 'A') {
            StringBuilder newSb = new StringBuilder(sb);
            newSb.deleteCharAt(sb.length() - 1);
            dfs(newSb);
        }
    }
}

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main {
    static int k;
    static String s, t;
    static int result;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        t = br.readLine();
        k = t.length();
        result = dfs(s, t);
        System.out.println(result);
 
    }
 
    public static int dfs(String s, String t) {
        if (s.length() == t.length()) {
            if (s.equals(t)) {
                return 1;
            }
            return 0;
        }
        int ans = 0;
        if (t.charAt(0) == 'B') {
            String substring = t.substring(1);
            StringBuilder sb = new StringBuilder(substring);
            String string = sb.reverse().toString();
            ans += dfs(s, string);
        }
 
        if (t.charAt(t.length() - 1) == 'A') {
            ans += dfs(s, t.substring(0, t.length() - 1));
        }
        return ans > 0 ? 1 : 0;
    }
}

 

---

 

4. 배운 점

- 하나씩 추가해가면서 나가는게 아니고 왜 완성된 문자열을 뺄 생각을 그렇게 못했을까..? 항상 반대로도 생각해보자

- StringBuilder를 삭제, 뒤집기 같은 연산을 자주 할 경우 값이 이상해질 수 도 있다. 그렇기에 새로운 객체를 생성해서 dfs를 하는것이 좋다.