4460 - 허프만 코딩

• Submit
• Status
• Discuss
• Summary

Description

 

허프만 코딩이란 문자의 빈도에 따라서 다른 길이의 부호를 사용하는 압축 알고리즘입니다. 이 알고리즘에서는 허프만 코딩 트리라 불리우는 이진 트리를 사용합니다. 허프만 코딩 트리를 만드는 방법은 다음 그림을 참고하길 바랍니다.

그림에서 총 5개의 문자가 있으면 각 문자의 빈도는 s(4), i(6), n(8), t(12), e(15) 입니다. 각각의 문자는 위 과정을 거쳐 다음과 같이 bit로 인코딩 됩니다.

s=111, i=110, n=10, t=01, e=00 

입력으로 문자열이 주어졌을 때, 허프만 코딩 트리를 만들고 어떠한 문자로 인코딩 되는지 구하는 프로그램을 작성하세요. 

Input

* Line 1 : 테스트개수T (1~100 범위의 정수)

* Line 2 ~ T+1 : 알파벳 소문자만으로 이루어진 문자열  (문자열의 길이는 1000을 넘지 않음)

 

Output

* Line 1 ~ T : 허프만 코딩으로 인코딩된 문자열 

Sample Input

1
withcswithcomputerscience

Sample Output

00011010110011110010000110101100111100000010010100000001011100010110010111011000101011100

Source

c자료구조8장