티스토리 뷰
코드
/**
* 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로 실행될 가능성이 극히 드물것임(평균시간복잡도 구해보기)
'[ Basic ] > # 알고리즘' 카테고리의 다른 글
[백준] 2206 : DFS와 BFS차이 (0) | 2022.02.13 |
---|---|
크루스칼(MST) vs 다익스트라 비교 (0) | 2022.02.03 |
[백준] 이중 우선순위 큐 (TreeMap) (0) | 2022.01.17 |
[DS] 레드블랙트리 (0) | 2022.01.11 |
[BinarySearch] 백준 1920 (0) | 2021.08.04 |
- Total
- Today
- Yesterday
- kafka
- go
- 우분투
- docker
- rolling update
- 카프카
- helm
- K8s
- 컨트롤러
- jvm
- ubuntu
- 쿠버네티스
- Java
- ci/cd
- Non-Blocking
- LFCS
- github actions
- GitOps
- argocd
- spring
- container
- golang
- 코틀린
- RDB
- db
- CICD
- Kubernetes
- Linux
- Controller
- Stream
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |