[Hackerrank] 1Week + Day7

Day 7 Interview Questions | HackerRank

1 Week의 마지막인 7 Day에는 Mock test가 없어 바로 추가 문제로 넘어가도록 하겠습니다. 🤗

 

1. Tree: Preorder Traversal

전위순회 결과를 출력하는 문제입니다.

 

def preOrder(root):
    if not root: return
    #Write your code here
    print(root.info, end=" ")
    preOrder(root.left)
    preOrder(root.right)

 

2. Tree: Huffman Decoding

주어진 문자열에서 Huffman Decoding을 수행하는 문제인줄 알아서 긴장하였지만,

실상은 Huffman Decoding이된 트리를 입력으로 주어지고, 디코딩 결과를 다시 문자열로 변경하면 되는 문제입니다.

 

1일 때는 오른쪽, 0일 때는 왼쪽 노드로 이동하면서

현재 노드가 리프노드일 때 해당 문자열을 결과 문자열에 추가해준 후, 다음 탐색을 위해 다시 root로 이동하면 됩니다. 👍🏻

def decodeHuff(root, s):
    #Enter Your Code Here
    cur = root
    result = ''
    for value in s:
        if value == '1':
            cur = cur.right
        else:
            cur = cur.left
        if not cur.left and not cur.right:
            result += cur.data
            cur = root
    print(result)

 

3. No Prefix Set

어느 한 단어가 다른 단어의 prefix인지 검사하여, 결과에 따라 다른 문자열을 출력하는 문제입니다.

 

물론 2중 for문을 사용해 각 문자열을들 비교할 수도 있지만,

이럴 경우에는 효율적이지 못하다고 생각해 문자열의 문자들로 트리를 만들어 해당 경로에 문자가 있는지 검사하는 방식으로

결과를 찾을 수 있도록 구현하였습니다.

🌹 이런 방식으로 문자열을 트리로 만드는 알고리즘을 칭하는 단어가 있었던거 같은데 기억이 나지 않네요. 😭

 

암튼! 이를 위해 먼저 아래와 같이 클래스를 만들어주었습니다.

class Node:
    def __init__(self):
        self.child = [None] * 10
        self.count = 0

child는 다음으로 오는 문자 정보를 가지고 있으며, 각 문자의 아스키코드 - 97(a) 값이 index입니다.

 

전체적인 코드는 아래와 같습니다.

class Node:
    def __init__(self):
        self.child = [None] * 10
        self.count = 0

def push(root, word):
    cur = root
    for w in word:
        index = ord(w) - 97
        if not cur.child[index]: cur.child[index] = Node()
        cur = cur.child[index]
        if cur.count > 0: return False
    
    if any(cur.child): return False
    cur.count+=1
    return True
        
def noPrefix(words):
    # Write your code here
    root = Node()
    for word in words:
        result = push(root, word)
        if not result:
            print("BAD SET")
            print(word)
            return
    
    print("GOOD SET")