[문제해결을 위한 창의적 알고리즘] 이진 복원 (고급 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

문제해결을 위한 창의적 알고리즘 목록