[백준] 12919 시간복잡도 풀이

코드

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

import java.io.*;

public class Main {
    private static String S, T;

    private static final char A = 'A';
    private static final char B = 'B';

    public static void main(String[] args) throws IOException {
        init();

        var result = solve(T);

        var bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(result ? "1" : "0");
        bw.flush();
        bw.close();
    }

    private static boolean solve(String curT) {
        if (S.length() == curT.length()) {
            if (S.equals(curT))
                return true;

            return false;
        }

        var firstCh = curT.charAt(0);
        var lastCh = curT.charAt(curT.length() - 1);

        if (firstCh == A && lastCh == A) {
            return solve(curT.substring(0, curT.length() - 1));
        } else if (firstCh == A && lastCh == B) { // 이 경우 때문에 기본 완탐 경우보다 시간효율이 좋음
            return false;
        } else if (firstCh == B && lastCh == A) {
            return solve(curT.substring(0, curT.length() - 1)) || solve(new StringBuilder(curT).reverse().deleteCharAt(curT.length() - 1).toString());
        } else if (firstCh == B && lastCh == B) {
            return solve(new StringBuilder(curT).reverse().deleteCharAt(curT.length() - 1).toString());
        }

        return false;
    }

    private static void init() throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));

        S = br.readLine();
        T = br.readLine();
    }

}
/**
 * 소요시간: 0.124초
 * 시간복잡도: O(2^N) (N = T.length - S.length)
 * 공간복잡도: O(T.length + S.length) ~ O(N)
 */

 

 

시간복잡도 풀이

- worst case는 solve() 메소드에서 세 번째 조건문(if (firstCh == B && lastCh == A) 만 호출되는 경우임.

- 세 번째 조건문의 경우, 재귀를 두 번 호출하기 때문

- 따라서 시간복잡도를 T(n)이라 두면 다음과 같음 (재귀는 S, T 길이 차이만큼 호출되므로 N = T.length - S.length)

 

T(n) = 2T(n-1) + C1

 

위 시간복잡도 식을 반복대치 방식으로 풀어쓰면 다음과 같음 (Cx 는 상수, T(0) = 0, T(1) = 1)

 

 

 

T(n) = 2T(n-1) + C1
T(n) = 2(2T(n-2) + C2) + C1
T(n) = 2(2(2T(n-3) + C3) + C2) + C1
T(n) = 2(2(2(2T(n-4) + C4) + C3) + C2) + C1

.....

T(n) = 2^n + C

 

 

 

 

결국 빅-오는 오더 2의 지수승 형태가 맞지만, 최악의 경우로 실행될 경우는 극히 드물다고 판단됨

- 이유 : 우선 if문이 4개인데, 네 가지 경우 모두 발생할 가능성이 각각 1/4 임.

- 특히, 두 번째 if문의 경우, 더 이상 재귀를 호출하지 않고 return 해버린다는 점도 고려해야 함

- 만약, 일반적인 재귀를 이용한 완전탐색 방식으로 풀었다 하더라도, 매 단계마다 재귀를 총 두 번씩 호출해야 하므로 빅-오가 2^n으로 동일하겠지만, 이렇게 풀었을 경우에는 매 단계마다 재귀 두 번을 '무조건적으로' 호출해야 하기 때문에 2의 지수승 타임으로 실행될 것 

- 하지만 지금 풀이의 경우에는 worst case로 실행될 가능성이 극히 드물것임(평균시간복잡도 구해보기)