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

}

}

Big O(nlogn) : n은 주어진 문자열 길이 (길이를 반으로 나눠가며 모든 문자를 확인해야 함)

GitHub: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/BinaryEncryptionSol61.java

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