LeetCode[ 208 | Python ] Implement Trie

문제

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

제목 그대로 자료구조 Trie를 구현해서 해결해야 하는 문제이다.

풀이

재귀

실행시간 : 154ms 메모리 : 38.9MB

입력은 각 함수를 호출하는 명렁어와, 그 안에 들어가는 데이터이나 신경쓰지 않고 함수만 구현하면 된다.
Trie의 각 기능을 구현하기 위해서는 재귀와 반복문을 사용할 수 있는데, 먼저 이를 재귀로 구현했다.

1. 초기화
   1. 초기화 함수 __init__ 에 root 정보를 담기 위해 해당 노드가 단어의 끝인지 판단할 수 있는 isEndOfWord와 해당 노드의 다음 노드로 이동할 수 있는 children을 기본적으로 key 값으로 준다.
2. insert 단어를 저장하는 함수
   1. 재귀를 구현하기 위해 내부함수 insert 를 구현한다.
      1. 저장하려는 철자를 얻어내기 위한 인덱스 idx와 현재 탐색하려는 노드 node를 인자로 받는다.
      2. 저장하려는 철자 word[idx] 가 현재 노드의 자손 노드안에 포함 되지 않으면, 그 자손 노드로 저장한다.
      3. 포함된다면 현재 탐색하려는 노드를 현재 철자의 노드로 변경한다.
      4. 인덱스 idx가 word의 길이를 벗어나면, 단어의 끝을 알리기 위해 isEndOfWord를 True 로 변경한다.
      5. 위 과정을 재귀적으로 수행한다.
   2. 내부함수 insert를 호출한다.
3. search 검색하려는 단어의 여부를 반환하는 함수.
   1. 재귀 호출을 위한 내부함수 search를 구현한다.
      1. 현재 탐색하려는 노드 node와 문자에서의 주소값 idx를 매개변수로 입력받는다.
      2. 현재의 철자 word[idx]가 현재 노드의 자손 노드에 포함된다면 다음 노드로 이동한다.
      3. 현재의 철자가 자손 노드에 포함되지 않는다면 False를 반환한다.
      4. 주소값 idx가 word의 길이를 벗어나면 단어의 끝인지를 알리는 isEndOfWord의 값을 반환한다.
      5. 위 과정을 재귀적으로 수행한다.
   2. 내부함수 search를 호출한다.
4. startsWith 접두어를 포함하는 단어의 여부를 반환하는 함수.
   1. 재귀 호출을 위한 내부함수 startsWith을 구현한다.
      1. 주어진 접두어를 search와 같은 방식으로 구현한다.
      2. 다만, 단어의 종료 여부 isEndOfWord에 따르지 않고 주소값이 접두어의 길이를 벗어나면 True를 반환한다.
   2. 내부함수 startsWith을 호출한다.

이와 같이 Trie를 재귀로 구현했다.
하지만 여기서 그치지 않고, 반복문과의 성능 비교를 위해 반복문으로 이를 구현하고 그 성능을 비교하고자 했다.

class Trie(object):
    root = {}

    def __init__(self):
        self.root['children'] = {}
        self.root['isEndOfWord'] = False
        

    def insert(self, word):
        def insert(node, idx):
            if idx >= len(word):
                node['isEndOfWord'] = True
                return

            c = word[idx]

            if not c in node['children']:
                node['children'][c] = {'children' : {}, 'isEndOfWord' : False}
            
            child = node['children'][c]
            insert(child, idx + 1)
        

        insert(self.root, 0)
        
    def search(self, word):
        def search(node, idx = 0):
            if idx >= len(word):
                return node['isEndOfWord']

            c = word[idx]
        
            if not c in node['children']:
                return False
            
            return search(node['children'][c], idx + 1)

        return search(self.root)
        
    def startsWith(self, prefix):
        def startsWith(node, idx = 0):
            if idx >= len(prefix):
                return True

            p = prefix[idx]
            
            if not p in node['children']:
                return False

            return startsWith(node['children'][p], idx + 1)

        return startsWith(self.root)

반복문

1. 초기화
   1. 초기화는 재귀 구현과 동일하다.
2. insert
   1. cur의 현재 탐색 노드 root를 저장한다.
   2. 주어진 단어 word를 순회한다.
      1. 현재 탐색하고 있는 철자 c가 현재 노드에 포함되지 않으면 이를 추가한다.
      2. 현재 노드를 현재 탐색하고 있는 노드로 변경한다.
   3. 순회가 끝나면 현재 노드의 isEndOfWord에 True 값을 저장하여 단어의 끝을 알린다.
3. search
   1. cur의 현재 탐색 노드 root를 저장한다.
   2. 주어진 단어 word를 순회한다.
      1. word의 현재 탐색하고 있는 철자 c가 현재 노드의 자손 노드에 포함되지 않으면 False를 반환한다.
   3. 현재 노드의 단어 종료 여부 isEndOfWord의 값을 반환한다.
4. startsWith
   1. 접두어 prefix에 대해 search와 같이 구현한다.
   2. 다만 단어 종료 여부에 관계 없이 반복문이 종료 된다면 True를 반환한다.

class Trie(object):
    root = {}

    def __init__(self):
        self.root['children'] = {}
        self.root['isEndOfWord'] = False
        

    def insert(self, word):
        cur = self.root
        
        for c in word:
            if(not c in cur['children']):
                cur['children'][c] = {'children' : {}, 'isEndOfWord' : False}

            cur = cur['children'][c]
        
        cur['isEndOfWord'] = True

    def search(self, word):
        cur = self.root

        for c in word:
            if(not c in cur['children']):
                return False
            cur = cur['children'][c]
        
        return cur['isEndOfWord']
        

    def startsWith(self, prefix):
        cur = self.root

        for p in prefix:
            if not p in cur['children']:
                return False
            cur = cur['children'][p]
        return True
        

생각 & 정리

이렇게 Trie를 재귀문과 반복문으로 구현해보았다.
재귀의 경우 코드가 단순해지지만 조금더 고려해야할 점이 많다는 생각이 들었고, 반복문의 경우 코드 내부를 생각하기에 훨씬 간단했다.
또한 실행시간도 평균 30ms 가량 재귀 구현에 비해 빠른 모습을 보였다.

그러면, Trie 구현해는 반복문이 제격인걸까 ?

그렇지는 않을 것 같다.

이 문제는 입력 받는 단어가 저장이 되어 있는지에 대한 여부만을 판단하면 되기 때문에 반복문으로 구현하기에 간편 했을뿐이며, 실제로 단어 자동완성을 구현한다고 생각했을 때 입력 받은 철자가 가지는 모든 자손노드에 대해 탐색을 수행하고자 한다면 반복문의 코드가 더욱 복잡해질 것이라는 생각이 들었다.

개발하거나, 개발을 공부하는 중에서나 항상 무엇이 옳다는 없듯이, 상황에 맞추어 반복문과 재귀를 적절히 섞어 사용하는 것이 옳겠다는 생각을 했다.