[문제해결을 위한 창의적 알고리즘] 허프만 인코딩 (고급, 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

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