[해커랭크] Tree: Huffman Decoding (C++)

문제 링크: www.hackerrank.com/challenges/tree-huffman-decoding/problem?h_r=internal-search

Tree: Huffman Decoding | HackerRank

1. 주의할 점

- 파라미터로 받았던 Tree의 Root를 저장하는 포인터가 있어야 한다

- Leaf에 도달했을 때 처리를 명확히 한다

 

2. 구현

- Head를 통해 Root 포인터를 기억해놓는다

- 모든 문자를 방문할때까지만 While문을 돌리도록 idx와 len을 통해 조건문을 설정한다

- 파라미터로 넘겨 받은 문자열 S에서 현재 가라키는 값을 C에 저장하고 C가 1이라면 오른쪽, 0이라면 왼쪽을 향한다. 이때, 향한 원소가 Leaf인지 판단하여 Leaf라면 Leaf에 저장된 문자를 출력하고 Root에 Head값을 대입한다

- isLeaf() 함수를 통해 해당 Node가 Leaf인지 판단한다

- 한번의 탐색이 끝날때 마다 idx++을 시켜서 S의 다음 문자를 C가 가리키도록 설정한다 

bool isLeaf(node* node){
    if(node->left==nullptr && node->right==nullptr) return true;
    return false;
}

void decode_huff(node * root, string s) {
    node* head = root;
    int idx = 0;
    int len = s.size();
    while(idx<len){
        char c = s[idx];
        if(c=='1'){     //오른쪽
            if(isLeaf(root->right)){      //leaf
                cout<<root->right->data;
                root=head;
            }
            else{
                root = root->right;
            }
        }
        else{       //왼쪽
            if(isLeaf(root->left)){      //leaf
                cout<<root->left->data;
                root=head;
            }
            else{
                root = root->left;
            }
        }
        idx++;
    }
}