(Medium) 허프만 코딩

허프만 코딩

: 데이터 문자의 등장 비도수에 따라서 다른 길이의 부호화를 사용하는 알고리즘

 

문제 링크

: Tree: Huffman Decoding | HackerRank

풀이 :

"""class Node:
    def __init__(self, freq,data):
        self.freq= freq
        self.data=data
        self.left = None
        self.right = None
"""        

# Enter your code here. Read input from STDIN. Print output to STDOUT
def decodeHuff(root, s):
    

//여기서 핵심은, 단순 재귀로 짜면 안되고, leaf에서 다시 루트로 돌아가야한다는것.
//즉 두 스텝이건 세 스텝이건 원복해야하며 순차적 원복이 아니다. 이럴땐 포인터 개념을 쓰자.
    result = ""
    curNode = root
    index = 0
    
    while index < len(s):
        if s[index] == "1":
            curNode = curNode.right
        else:
            curNode = curNode.left
        
        if not curNode.right and not curNode.left:
            result += curNode.data        
            curNode = root //Key Point !!
        
        index += 1
    print(result)