문자를 압축하자 - 문제

문제 설명

1952년 David Huffman에 의해 개발된 허프만 인코딩은 문자의 출혈 빈도에 따라 가변 길이의 부호를 사용하는 압축 알고리즘이다. 허프만 알고리즘은 각 문자를 2진 순서를 이용해서 자주 등장하는 문자에게는 비트를 작게 할당하고, 드문 문자에게는 많은 비트를 할당하는 방식을 이용하고 있다. 보통 이진트리형태로 표현하며 문자를 단말노드에 배치하고, 모든 문자의 2진 순서는 다르게 나타낸다.
다음과 같은 이진트리에 문자가 배치되어 있다고 가정하면,
A는 0, B는 10, C는 110, D는 111로 코드를 갖게 된다.

허프만 코드가 주어졌을 때 압축된 데이터(2진수)를 원래의 문자로 출력해보자

입력 설명

첫 줄에 정수 k(1 <= k <= 30)가 입력된다. k는 허프만 코드의 문자 개수를 의미한다.
다음 줄부터는 k개의 문자(문자는 a~z, A~Z 중에 선택)와 압축된 이진코드 값이 공백으로 구분하여 입력(최대 30비트)된다
마지막 줄에는 200자 이하의 압축된 데이터(2진수)가 입력된다.

출력 설명

압축된 데이터(2진수)가 원래의 문자로 출력된다.

입력 예시 Copy

출력 예시 Copy

BCBBA

출처/분류