3. [Python] 프로그래머스 2020 카카오 블라인드 채용 : 가사 검색 - 코딩도치

안녕하세요. 코딩도치입니다~

 

오늘은 프로그래머스에 있는 2020 카카오 블라인드 채용 : 가사 검색 문제를 풀어보려고 합니다!

 

위 문제는 트라이(Trie) 자료구조를 사용하여 풀어야 효율성 테스트를 통과할 수 있습니다.

 

먼저, 트라이(Trie) 자료구조에 대해서 알아보겠습니다.

 

트라이(Trie) 자료구조

 

트라이는 문자열을 트리 형태로 저장하는 문자열 검색에 특화된 자료구조입니다.

 

트라이 자료구조를 사용하게 되면 가장 긴 문자열의 길이가 N이라고 했을 때, O(N)의 시간복잡도로 문자열을 찾을 수가 있습니다.

 

["app", "apart", "away", "bear"] 의 문자열이 주어졌을 때, 트라이 자료구조가 만들어지는 과정은 다음과 같습니다.

 

트라이 자료구조는 아무 데이터도 들어 있지 않은 루트 노드부터 시작합니다.

 

각 단어마다 반복을 돌면서 각 단어의 알파벳을 저장하게 됩니다.

 

app이라는 단어를 트라이 구조로 만들게 되면 다음과 같습니다.

 

루트 노드부터 시작해서 자식 노드에 해당 알파벳이 없다면, 자식 노드로 알파벳을 추가하는 것입니다(a, p, p 알파벳을 순차적으로).

 

그리고 마지막 알파벳이 들어왔을 때 해당 알파벳 노드에는 우리가 찾는 문자열이라는 표시를 해주어야합니다.

 

그래서 루트 노드부터 검색을 시작해서 마지막 p에 도착했을 때 우리는 app라는 문자열이 트라이에 있구나 파악할 수 있는 것입니다.

 

마찬가지 방식으로 apart를 트리 구조에 넣게 되면 되면 다음과 같은 트라이 자료구조가 만들어지게 됩니다.

 

a, p 까지는 이미 트리 구조로 들어가 있었기 때문에 따로 넣지 않고,

 

p 이후로 a 자식 노드가 없기 때문에 a 노드를 추가하는 것입니다. 마지막으로 apart의 끝에는 문자열이라는 표시를 해주었습니다.

 

이렇게 위 모든 문자열로 트라이 자료구조를 만들면 다음과 같습니다.

이렇게 트라이 자료구조를 만들어 놓고 루트노드부터 시작하여 찾고자 하는 문자열을 검색하는 것입니다.

 

이제 문제에 적용시켜보겠습니다.

 

가사 검색 문제의 핵심은 트라이 자료구조를 어떻게, 얼마나 만들 것인지를 파악하는 것입니다.

 

먼저 "for??"와 같이 접미사에 ?가 있는 경우

 

주어진 문자열들로 만들어진 트라이 자료구조로 for까지 검색한 후 그 이후로 나오는 단어의 개수를 파악하면 됩니다.

 

하지만 ???oop와 같이 접두사에 ?가 있는 경우

 

주어진 문자열을 그대로 사용하여 만든 트라이 자료구조로는 검색이 불가능합니다.

 

그래서 주어진 문자열들의 역순으로 만들어진 트라이 자료구조가 필요합니다.

 

???oop를 검색하는 것은 역순으로 만들어진 트라이 자료구조에서 poo???를 찾는 것과 동일하기 때문입니다.

 

그리고 단어의 길이 조건도 만족해야하기 때문에,

 

단어 길이마다 트라이 자료구조를 만들어주어야 합니다.

 

예를 들어

app은 문자열의 길이가 3인 트라이 자료구조

apply, apart는 문자열의 길이가 5인 트라이 자료구조

 

이렇게 길이를 구분하여 트라이를 각각 만들어 주는 것입니다.

 

그래서 a??와 같은 길이가 3인 검색 문자가 들어오면 길이 3짜리 트라이 자료구조에서 검색하고

 

ap???와 같이 길이가 5인 검색 문자가 들어오면 길이 5짜리 트라이 자료구조에서 검색하는 것입니다.

 

마지막으로 검색하고자 하는 문자의 접두사 이후로 트라이 자료구조에 몇개의 단어가 있는지 각 노드에 저장을 해주어야합니다.

 

그렇게 저장을 해두지 않고 끝까지 검색을 통해 단어의 개수를 파악하게 되면 트라이 자료구조를 사용하더라도 시간초과가 발생합니다.

 

이 문제에서는 중복되는 가사가 없기 때문에, 어떤 알파벳을 지나간다면 해당 노드 이후로 하나의 단어가 있다고 판단할 수 있습니다.

 

그래서 저장을 할때,

 

특정 노드를 지나갈 때 마다 각 노드의 카운트를 하나씩 증가시켜면 해당 노드 이후로 몇개의 단어가 있는지 바로 파악할 수 있습니다.

 

아래는 파이썬으로 구현한 소스입니다.

# 2020 카카오 블라인 코딩테스트 - 가사 검색

class Node(object):
    def __init__(self, key):
        self.key = key
        self.count = 0
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(self)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            curr_node.count += 1
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)

            curr_node = curr_node.children[char]

        curr_node.count += 1

    def starts_with(self, prefix):
        curr_node = self.head
        result = 0

        for char in prefix:
            if char == '?':
                break

            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return 0

        return curr_node.count


def solution(words, queries):
    answer = []
    tries = {}
    reverse_tries = {}

    for word in words:
        if len(word) in tries:
            tries[len(word)].insert(word)
            reverse_tries[len(word)].insert(reversed(word))
        else:
            trie = Trie()
            reverse_trie = Trie()

            trie.insert(word)
            reverse_trie.insert(reversed(word))

            tries[len(word)] = trie
            reverse_tries[len(word)] = reverse_trie

    for query in queries:
        if len(query) in tries:
            if query[0] != '?':
                trie = tries[len(query)]
                answer.append(trie.starts_with(query))
            else:
                trie = reverse_tries[len(query)]
                answer.append(trie.starts_with(reversed(query)))
        else:
            answer.append(0)

    return answer

 

감사합니다.