[문제해결을 위한 창의적 알고리즘] 이진 복원 (고급 p.62)
이 문제는 Queue를 이용하는 방법과 Queue를 이용하지 않는 방법 두가지를 소개하고 있으나, 여기서는 Queue 없이 푸는 방법을 소개하고자 한다.
'-'가 나타나면 길이를 반으로 나눠 다시 2개의 재귀 함수를 호출하는 방법으로 푼다.
import java.util.Scanner;
public class BinaryDecryptionSol67 {
public static char[] S = new char[1<<19];
public static char[] S2 = new char[1<<19];
public static int n, p;
public static String str;
//k는 복원 시작 지점, s는 길이
public static void f(int k, int s) {
char val = S[p++];
if (p==str.length()+1)
return;
// '-'이면 길이를 반으로 나눠 다시 재귀 호출
if (val=='-') {
f(k, s/2);
f(k+s/2, s/2);
}
// '-'이 아니면 길이 s만큼 채우기
else {
for (int i = k; i < k+s;i++)
S2[i] = val;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
str = sc.next();
S = str.toCharArray();
sc.close();
f(0, n);
System.out.println(S2);
}
}
Big O(nlogn) : n은 암호문자 길이
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/BinaryDecryptionSol67.java