허프만 부호화

허프만 부호화(Huffman coding)는 데이비드 허프만(David Huffman)이 1952년에 고안한 우아한 텍스트 압축 알고리즘이다.

핵심 아이디어는 각 문자에 이진 부호(0과 1로 이루어진 수열)를 할당하는 것이다. 이 부호들은 접두사 성질이 없는(prefix-free) 조건을 만족한다. 즉, 어떤 문자의 부호도 다른 문자의 부호의 접두사가 되지 않는다.

접두사 성질이 없는 부호를 만드는 간단한 방법은 문자들을 이진 트리의 잎(leaf)에 놓고, 모든 왼쪽 간선에는 0, 모든 오른쪽 간선에는 1을 붙이는 것이다. 루트에서 어떤 잎까지 내려가는 경로가 바로 그 잎에 있는 문자의 부호가 된다. 예를 들어 아래 이진 트리는 문자 {A, B, C, D, E}에 대한 접두사 없는 부호를 정의한다.

여기서 A는 00, B는 01, C는 10, D는 110, E는 111로 부호화된다.

부호가 접두사 성질이 없으므로, 이 부호들을 이어 붙인 어떤 수열도 항상 유일하게 원래 문자들로 복호화(decode)할 수 있다.

허프만 부호(문자들과 그에 대응하는 이진 부호의 집합)와 이진 수열이 주어질 때, 그 이진 수열을 원래 문자들로 복호화하여라.

첫째 줄에 문자의 개수 $k$ ($1 \le k \le 20$)가 주어진다. 다음 $k$개의 줄에는 각각 문자 하나, 공백 하나, 그리고 그 문자에 대응하는 이진 부호(길이는 최대 $10$)가 주어진다. 모든 문자는 알파벳 글자(a--z 또는 A--Z)이며, 주어지는 부호들은 접두사 성질이 없음이 보장된다.

그 다음 줄에는 복호화할 이진 수열이 주어진다. 이 수열은 주어진 부호들을 이어 붙여 만든 올바른 수열이며, 이진 숫자의 개수는 최대 $250$개이다.

주어진 이진 수열을 복호화한 문자들을 한 줄에 출력한다.