[문제해결을 위한 창의적 알고리즘] 허프만 인코딩 (고급, p125)
이 문제는 문제만 읽고 나서는 무언가 생략된 설명이 많은 듯한 문제다. 문제의 그림만 보고 가만히 생각해 보면 각 문자에 해당하는 값을 보고 암호화된 문자열 값을 하나씩 대입해 보는 것으로도 풀 수 있지 않을까라는 생각이 든다. 그렇다면 굳이 트리를 구현할 필요가 없기 때문이다.
그러나 문제에서 원하는 바는 트리를 탐색하는 것을 구현하고자 하는 것이다.
import java.util.Scanner;
public class HuffmanEncoding {
public static int k;
public static char[] longcode = new char[251];
public static char[] hufftree = new char[1<<20];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
k = sc.nextInt();
char c;
char[] code = new char[21];
for (int i = 0; i <k; i++){
c = sc.next().charAt(0);
code = sc.next().toCharArray();
int l =0;
int p =1;
// 각 문자와 코드에 대해서 트리로 만든다
while(l<code.length){
if (code[l++]=='0')
p*=2;
else
p=(p*2)+1;
}
hufftree[p]=c;
}
longcode = sc.next().toCharArray();
sc.close();
int lp=0;
int tp =1;
while(lp<longcode.length){
if (longcode[lp++]=='0')
tp*=2;
else
tp = (tp*2)+1;
// 해독할 문자열을 트리에서 찾아 출력한다
if (hufftree[tp]!='\0'){
System.out.print(hufftree[tp]);
tp=1;
}
}
return;
}
}
Big O(n): 해독할 문자열 길이
github 주소: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/HuffmanEncoding.java