Sicily 3703. Huffman Coding V1

Huffman 나무...자료를 찾아보니 구체적으로 어떻게 만들었는지 알 수 있다. 기본 절차는 다음과 같다.노드 집합에서 권한이 가장 적은 두 개의 노드를 찾아내고 작은 것이 왼쪽이고 큰 것이 오른쪽이며 집합에서 삭제한다.2. 위에서 찾은 두 노드를 하나로 합쳐 노드 집합에 추가한다.3. 상기 절차를 반복하여 하나의 노드만 남으면 이 노드가 뿌리 노드가 된다.4. 어떤 노드의 인코딩을 찾을 때 뿌리 노드에서 출발하여 왼쪽은 0이고 오른쪽은 1이다. 이 노드(필수잎)를 찾을 때까지 전체 과정은 이 노드의 인코딩이다.사실 허프맨 트리는 유일한 것이 아니다. 두 노드의 권한이 같을 때 좌우 트리가 확실하지 않기 때문이다.이 문제에서는 이런 상황을 어떻게 처리하는지 설명하지 않았다. 왜냐하면 데이터는 이런 상황이 나타나지 않기 때문이다(테스트), 모두가 원하는 대로 처리하기 때문이다.
Run Time: 0sec
Run Memory: 312KB
Code length: 1627Bytes
Submit Time: 2012-01-05 01:13:13

// Problem#: 3703
// Submission#: 1174156
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include 
#include 
#include 
using namespace std;

struct Node {
    string s;
    int weight;
    Node( string code, int n ) { s = code; weight = n; }
};

vector v;
vector::iterator it;

void encode( string s, int n ) {
    for ( it = v.begin(); it != v.end(); it++ ) {
        if ( n >= it->weight )
            break;
    }
    v.insert( it, Node( s, n ) );
}

int main()
{
    int n;
    int i;
    int keep;
    char c;
    string s, left, right;
    int freq[ 26 ] = { };
    string code[ 26 ] = { };

    cin >> n;
    while ( n-- ) {
        cin >> c;
        freq[ c - 'A' ]++;
    }

    for ( i = 0; i < 26; i++ ) {
        if ( freq[ i ] != 0 ) {
            s = 'A' + i;
            encode( s, freq[ i ] );
        }
    }

    while ( v.size() != 1 ) {
        left = v.back().s;
        for ( i = 0; i < left.size(); i++ )
            code[ left[ i ] - 'A' ] = '0' + code[ left[ i ] - 'A' ];
        keep = v.back().weight;
        v.pop_back();

        right = v.back().s;
        for ( i = 0; i < right.size(); i++ )
            code[ right[ i ] - 'A' ] = '1' + code[ right[ i ] - 'A' ];
        keep += v.back().weight;
        v.pop_back();

        encode( left + right, keep );
    }

    while ( true ) {
        keep = 0;
        for ( i = 1; i < 26; i++ ) {
            if ( freq[ i ] > freq[ keep ] )
                keep = i;
        }

        if ( freq[ keep ] != 0 ) {
            cout << (char)('A' + keep) << " " << freq[ keep ] << " " << code[ keep ] << endl;
            freq[ keep ] = 0;
        }
        else
            break;
    }

    return 0;

}