[문제해결을 위한 창의적 알고리즘] 이진 암호화 (고급 p.58)
이 문제는 주어진 길이 내의 문자가 모두 일치하지 않을 때, 길이를 반으로 나눠 다시 해당 길이내의 문자가 모두 같은지를 확인하는 방법을 묻고 있다. 이 아이디어만 잘 이해한다면 쉽게 풀 수 있는 문제로 보인다. 재귀호출을 통해 아래와 같이 구현할 수 있다. 모든 문자가 0 혹은 1인지를 판단하기 위해 각 숫자를 더한 것에 유의하시기 바랍니다.
import java.util.Scanner;
public class BinaryEncryptionSol61 {
// 필요한 문자열 길이를 << bit operation으로 지정
public static char[] S = new char[1<<19];
public static int n;
public static void f(int k, int s) {
int sum = 0;
// 길이가 1이면 바로 출력
if (s==1) {
System.out.print(S[k]);
return;
}
// 주어진 길이에 대해 해당 문자 값 (숫자)을 모두 더함
for (int i = k; i < k+s; i++)
sum += (S[i]-'0');
// 더한 값이 0이면 모두 0, 더한 값이 길이와 같으면 모두 1로 간주
if (sum == 0 || sum == s)
System.out.print(sum/s);
// 그렇지 않은 경우 길이를 반으로 나눠 다시 재귀 호출
else {
System.out.print("-");
f(k, s/2);
f(k+s/2, s/2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
// 문자열을 char type 배열에 배정
S = sc.next().toCharArray();
sc.close();
// 위치와 길이를 parameter로 지정하여 호출
f(0, n);
return;
}
}
GitHub: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/BinaryEncryptionSol61.java