프로그래밍 면접 문제 28: Longest Compound Word

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 27: Squareroot of a Number

정렬된 단어 목록이 주어지면, 이 목록에 있는 단어들을 연결해 가장 긴 합성어를 찾는 문제입니다. 예를 들어, 입력된 단어 목록이 [‘cat’, ‘cats’, ‘catsdogcats’, ‘catxdogcatsrat’, ‘dog’, ‘dogcatsdog’, ‘hippopotamuses’, ‘rat’, ‘ratcat’, ‘ratcatdog’, ‘ratcatdogcat’]인 경우, 가장 긴 합성어는 12자의 길이를 가진 ‘ratcatdogcat’입니다. 가장 긴 개별 단어는 14자의 ‘catxdogcatsrat’ 그리고‘hippopotamuses’ 이지만, 목록의 다른 단어로 완전하게 구성되지 않았습니다. ‘catxdogcatsrat’에는 ‘x’ 문자가 있고, ‘hippopotamuses’는 합성어가 아닌 개별 단어입니다.

이 문제를 해결하는데 prefix tree라고도 알려진 트라이(trie)를 사용합니다. 트라이는 텍스트 저장 및 검색에 공간과 시간면에서 효율적인 자료 구조입니다. 트라이는 단어들이 접두어를 공유하도록하며, 이는 이 문제에서 처리해야 하는 것과 정확하게 일치합니다. 이전 포스트 Find Word Positions in Text 에서 트라이 구현 방법에 대한 샘플을 참고할 수 있습니다. 이 문제에서는 이전과 다른 노드 정의 및 두 개의 추가적인 Trie 클래스 함수를 가진 변형된 버전을 사용합니다.

class Node:
    def __init__(self, letter = None, isTerminal = False):
        self.letter = letter
        self.children = {}
        self.isTerminal = isTerminal

def insert(self, word):
    current =self.root
    for letter in word:
        if letter not in current.children:
            current.children[letter] = Node(letter)
        current = current.children[letter]
    current.isTerminal = True
 
def getAllPrefixesOfWord(self, word):
    prefix = ''
    prefixes = []
    current = self.root
    for letter in word:
        if letter not in current.children:
            return prefixes
        current = current.children[letter]
        prefix += letter
        if current.isTerminal:
            prefixes.append(prefix)
    return prefixes

Node 클래스의 isTerminal 필드는 루트에서 현재 노드까지의 문자로 구성된 단어가 유효한 단어라는 것을 의미합니다. 예를 들어 cat이라는 단어는 각 문자에 대해 3개의 노드로 구성됩니다. 그리고 마지막 문자 ‘t’는 isTerminal 값이 True 입니다.

트라이의 insert 함수는 트라이에 주어진 단어를 추가하는 기능을 합니다. 이보다 더 중요한 getAllPrefixesOfWord 함수는 단어를 입력 받고, 이 단어에서 유효한 접두어를 모두 반환합니다. 여기에서 유효하다는 것은 입력 목록에 나타난다는 것을 의미합니다. 여기에서 정렬된 목록이 도움이 됩니다. 목록을 처음부터 확인하는 동안 현재 단어의 모든 접두어는 이미 확인되어 트라이에 추가되어 있습니다. 따라서 단어의 문자 노드를 가진 루트에서부터 단일 경로를 따라가면서 isTerminal이 true 값을 가지는 노드에 해당하는 접두어 단어를 반환해서, 특정 단어가 가진 모든 접두어를 찾는 작업을 쉽게 처리할 수 있습니다.

알고리즘은 다음과 같이 동작하는데, 입력 목록을 처음부터 확인해가면서 트라이에 각 단어를 삽입합니다. 단어 삽입을 한 뒤 이 단어에 접두어가 있는지 확인합니다. 접두어를 가진 경우, 이 단어는 가장긴 합성어가 될 후보 중 하나입니다. 현재 단어와 이 단어의 접미사 (단어-접두어)를 쌍으로 큐(queue)에 추가합니다. 이렇게 하는 이유는 접미사가 유효한 단어 또는 합성어인 경우에만 현재 단어가 유효하게 구성되기 때문입니다. 따라서 배열을 확인하는 과정에서 트라이와 큐를 생성합니다.

예제를 통해서 이 과정을 살펴보겠습니다. 첫 번째 단어는 cat이고 이를 트라이에 추가합니다. cat에는 접두어가 없기 때문에 계속 진행합니다. 두 번째 단어는 cats이고 이를 트라이에 추가한 다음 접두어가 있는지 확인해보면 단어 cat이라는 접두어를 가지고 있다는 것을 알 수 있습니다. 따라서 현재 단어와 접미사 <‘cats’, ‘s’> 쌍을 큐에 추가합니다. 세 번째 단어는 catsdogcats이고 이 단어를 다시 트라이에 추가합니다. 여기에는 cat과 cats 이렇게 2개의 접두어가 포함되어 있습니다. 따라서 <‘catsdogcats’, ‘sdogcats’> 와 <‘catsdogcats’, ‘dogcats’> 2개의 쌍을 큐에 추가합니다. 여기에서 이전 쌍의 접미사 sdogcats는 접두어 cat에 해당되고 나중의 쌍의 접미사 dogcats는 접두어 cats에 해당됩니다. 이런 방식으로 <‘catxdogcatsrat’, ‘xdogcatsrat’>를 큐에 추가하며, 작업을 계속 진행합니다. 다음은 예제를 추가해서 만든 트라이 입니다.

트라이와 큐를 생성한 다음 큐의 처음부터 쌍(pair)을 빼내 작업을 처리합니다. 위에서 설명한대로 큐에 추가된 쌍에는 원래 단어와 유효성 검사를 위한 접미사가 포함되어 있습니다. 접미사가 유효한 단어 또는 합성어인지 확인합니다. 접미사가 유효한 단어이고 원래 단어가 지금까지 가장 긴 경우, 이 결과를 저장합니다. 그렇지 않은 경우 이 쌍을 버립니다. 접미사는 그 자체로 합성어일 수 있기 때문에, 접미사에 접두어가 포함되어 있는지 확인합니다. 접미사에 접두어가 포함되어 있는 경우, 원래 단어와 해로운 접미사를 큐에 추가해서 위의 절차를 적용합니다. 큐에서 빼낸 원래 쌍(pair)의 접미사가 유효한 단어도 아니고 접두어도 포함하지 않는 경우, 해당 쌍을 버립니다.

예제를 통해서 이 과정을 명확히 해보겠습니다. 큐에서 빼낸 단어 쌍 <‘catsdogcats’, ‘dogcats’>를 확인합니다. Dogcats는 유효한 단어가 아니기 때문에 접두어가 포함되어 있는지 확인합니다. Dog는 접두어고, cats는 새로운 접미사가 됩니다. 따라서 <‘catsdogcats’, ‘cats’>를 큐에 추가합니다. 다음에 이 쌍이 큐에서 나오면 cats가 유효한 단어라는 것을 확인하고 catsdogcats라는 단어를 처리합니다. 반복 과정을 거치면서 접미사는 점점 짧아지고 단어 쌍은 어느 순간 버려지거나 가장 긴 단어로 저장된다는 것을 볼 수 있습니다. 단어 쌍이 버려지면 큐의 길이가 줄어들면서 알고리즘이 점차적으로 끝에 이릅니다. 다음은 이 알고리즘을 완전히 구현한 코드입니다:

def longestWord(words):
    #Add words to the trie, and pairs to the queue
    trie=Trie()
    queue = collections.deque()
    for word in words:
        prefixes = trie.getAllPrefixesOfWord(word)
        for prefix in prefixes:
            queue.append( (word, word[len(prefix):]) )
        trie.insert(word)
 
    #Process the queue
    longestWord = ''
    maxLength = 0
    while queue:
        word, suffix = queue.popleft()
        if suffix in trie and len(word) > maxLength:
            longestWord = word
            maxLength = len(word)
        else:
            prefixes = trie.getAllPrefixesOfWord(suffix)
            for prefix in prefixes:
                queue.append( (word, suffix[len(prefix):]) )
 
    return longestWord

이 알고리즙의 복잡도는 O(kN)이며, 여기에서 N은 입력 목록의 단어 수이고 k는 합성어의 최대 단어 수입니다. 숫자 k는 목록마다 다를 수 있지만 일반적으로 5 또는 10과 같은 일정한 숫자입니다. 따라서 알고리즘은 입력 목록에 비례하고 이는 이 문제에 최적화된 해결 방법입니다.

다음은 트라이의 구현을 완성한 코드입니다.

class Trie:
    def __init__(self):
        self.root = Node('')
 
    def __repr__(self):
        self.output([self.root])
        return ''
 
    def output(self, currentPath, indent=''):
        #Depth First Search
        currentNode = currentPath[-1]
        if currentNode.isTerminal:
            word=''.join([node.letter for node in currentPath])
            print indent + word
            indent += '  '
        for letter, node in sorted(currentNode.children.items()):
            self.output(currentPath[:]+[node], indent)
 
    def insert(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children:
                current.children[letter] = Node(letter)
            current = current.children[letter]
        current.isTerminal=True
 
    def __contains__(self, word):
        current=self.root
        for letter in word:
            if letter not in current.children:
                return False
            current = current.children[letter]
        return current.isTerminal
 
    def getAllPrefixesOfWord(self, word):
        prefix = ''
        prefixes = []
        current = self.root
        for letter in word:
            if letter not in current.children:
                return prefixes
            current = current.children[letter]
            prefix += letter
            if current.isTerminal:
                prefixes.append(prefix)
        return prefixes