백준 6800번 C++ 풀이

https://www.acmicpc.net/problem/6800

6800번: Huffman Encoding

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	실버 3

문제

There is an ingenious text-compression algorithm called Huffman coding, designed by David Huffman in 1952.

The basic idea is that each character is associated with a binary sequence (i.e., a sequence of 0s and 1s). These binary sequences satisfy the prefix-free property: a binary sequence for one character is never a prefix of another character’s binary sequence.

It is worth noting that to construct a prefix-free binary sequence, simply put the characters as the leaves of a binary tree, and label the “left” edge as 0 and the ”right” edge as 1. The path from the root to a leaf node forms the code for the character at that leaf node. For example, the following binary tree constructs a prefix-free binary sequence for the characters {A, B, C, D, E}:

That is, A is encoded as 00, B is encoded as 01, C is encoded as 10, D is encoded as 110 and E is encoded as 111.

The benefit of a set of codes having the prefix-free property is that any sequence of these codes can be uniquely decoded into the original characters.

Your task is to read a Huffman code (i.e., a set of characters and associated binary sequences) along with a binary sequence, and decode the binary sequence to its character representation.

입력

The first line of input will be an integer k (1 ≤ k ≤ 20), representing the number of characters and associated codes. The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10) representing the associated code of that character. You may assume that the character is an alphabet character (i.e., ‘a’...‘z’ and ‘A’..‘Z’). You may assume that the sequence of binary codes has the prefix-free property. On the k + 2nd line is the binary sequence which is to be decoded. You may assume the binary sequence contains codes associated with the given characters, and that the k + 2nd line contains no more than 250 binary digits.

출력

On one line, output the characters that correspond to the given binary sequence.

---

랜실디를 하겠다고 마음먹고 또 안해버린 나는 이번엔 교내대회가 있어서 다시 시작했다... 그냥 꾸준히 하면 될걸 참 게으른 나자신이 한심하다.

 

각설하고, 문제가 영어라고 쫄지 말자. 이정도면 읽을만 하다. 입력으로 들어오는 알파벳과 각 알파벳에 대응하는 코드가 주어진다. 이를 통해 트리를 구성하고 나서, 만들어진 트리를 통해 디코딩할 허프만 코드가 들어오고, 그 코드를 트리를 통해 디코딩하면 된다.

 

트리를 사용할줄 알면 쉬운 문제인데, 이게 문제는 입력제한조건이 문제에서 제시한 조건과 다르다.  (https://www.acmicpc.net/board/view/85193)

글 읽기 - 입력 조건을 변경해 주세요.

 

이거때문에 계속해서 segmentation fault 런타임 에러가 발생하게되었다. 길이 제한 10인줄알고 트리(배열로 구성했음)의 길이를 적당히 2^12로 맞춰놓았는데 계속해서 발생했다. 나중에 질문 게시판에 저 글이 올라와있는걸 확인했고, 길이 제한 2^20(대충 105만쯤)에 맞게 2 * 10^6으로 바꿨더니 정답이었다... 문제 오타 안고치는건 좀 그렇지 않나?

 

이제 허프만 코드 문제 풀이를 해보면, 일단 알파벳에 대응하는 코드를 저장해둔다. 그리고 트리를 잘 보면 이진코드에서 0이면 왼쪽, 1이면 오른쪽으로 이동하기 때문에, 이 조건에 맞춰서 트리(배열)의 인덱스에 2를 곱하고 1을 더하거나 말거나 해서 인덱스를 조정하며 해당 위치에 알파벳을 입력한다. 모든 입력에 대해 이 행위를 완수하면 우리는 허프만 코드 디코딩을 위한 트리를 완성했다.

 

이후에는 디코딩할 코드를 보며 0, 1코드에 맞추어 루트 노드에서 이동한다. 그리고 이동한 노드에서 알파벳이 있는 경우, 해당 알파벳을 기록하고, 다시 루트노드로 돌아가기를 반복한다.

 

#include <bits/stdc++.h>
using namespace std;

map<string, string> wordCode; // 알파벳 코드 저장
string hufCode; // 디코딩할 허프만코드
array<string, (int)(2e6)> wordTree; // 트리 구성

void input() {
    int n;

    cin >> n;
    string word, code;

    for(int i = 0; i < n; i++) {
        cin >> word >> code;
        wordCode.insert({word, code}); // 알파벳, 코드 저장
    }

    cin >> hufCode;
}

void setTree() {
    wordTree.fill("-"); // 트리 초기화. - 는 비어있다는 뜻
    int idx;

    for (auto iter = wordCode.begin(); iter != wordCode.end(); iter++) {
        idx = 1; // 시작 위치
        for(auto x : iter->second) {
            if (x == '0') idx *= 2; // 0이면 왼쪽
            else idx = idx * 2 + 1; // 1이면 오른쪽
        }
        wordTree[idx] = iter->first; // 구한 인덱스에 문자 삽입
    }
}

void sol() {
    setTree(); // 허프만 트리 구성
    
    string answer;
    int idx = 1;

    for (int i = 0; i < hufCode.length(); i++) {
        if (hufCode[i] == '0') idx *= 2;
        else idx = idx * 2 + 1;

        if (wordTree[idx] != "-") { // 만약 해당 노드에 값이 존재하면
            answer += wordTree[idx]; // 알파벳 기록하고
            idx = 1; // 루트로 돌아간다.
        }
    }
    cout << answer;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}