[프로그래머스/Python] 가사 검색 (2020 KAKAO BLIND RECRUITMENT)

📌 문제 탐색하기

• 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 구하기
• 키워드는 와일드카드 문자 중 하나인 '?'가 포함된 패턴 형태의 문자열
  • '?'는 글자 하나를 의미, 어떤 문제에도 매칭됨
  • "fro??" => "frodo"(O), "front"(O) / "frame"(X), "frozen"(X)
• 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하기
• 가사 단어 제한 사항 
  • 2 ≤ words의 길이 ≤ 100,000
  • 1 ≤ 각 가사의 단어 길이 ≤ 10,000
  • 2 ≤ 전체 가사 단어 길이의 합 ≤ 1,000,000
  • 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공
  • 각 가사 단어는 오직 알파벳 소문자로만 구성
• 검색 키워드 제한 사항
  • 2 ≤ queries의 길이 ≤ 100,000
  • 1 ≤ 각 검색 키워드의 길이 ≤ 100,000
  • 2 ≤ 전체 검색 키워드 길이의 합 ≤ 1,000,000
  • 검색 키워드는 중복될 수 있으며, 오직 알파벳 소문자와 와일드 카드 문자 '?'로만 구성
  • 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함, '?'는 각 검색 키워드의 접두사 혹은 접미사

queries에 포함된 각 검색 키워드를 하나씩 순회하면서, 와일드 카드 문자가 있는 위치를 제외한 위치의 문자들이 일치하는지 하나씩 확인하려면 최악의 경우 총 시간복잡도가 약 O(100,000)(queries에 있는 검색 키워드 하나씩 순회) * O(100,000)(words의 단어들 하나씩 순회) * O(10,000)(와일드 카드를 제외한 부분 일치 여부 체크) 정도가 된다. 당연히 매우 비효율적이며 더욱 효율적인 방법을 찾아야한다.

 

해당 문제에서 와일드 카드는 반드시 각 검색 키워드의 접두사 혹은 접미사라고 했으므로, 문자열의 공통 접두사를 효율적으로 관리하며, 접두사나 접미사를 효율적으로 검색할 수 있는 Trie 자료구조를 사용하면, 탐색 시간을 단축할 수 있다.

 

Trie(트라이) 자료구조
문자열을 효율적으로 저장하고 검색하기 위한 트리(Tree) 자료구조
주로 문자열을 키로 가지는 데이터를 관리하는 데 사용되며, 문자열의 접두사(prefix)를 기반으로 데이터를 구성하기 때문에 Prefix Tree라고도 불린다.

 

📌 코드 설계하기

1. class TrieNode 구현
   • 트라이 자료구조의 각 노드를 표현할 클래스
   • 프로퍼티
     • children: 각 노드의 하위 노드를 딕셔너리 형태로 저장. 문자(char) 하나와 그 다음 문자에 해당하는 TreeNode 객체를 키-값으로 가짐
     • length_count: 해당 노드를 시작으로 이어지는 문자열들의 길이에 따른 개수를 딕셔너리 형태로 저장. 해당 노드 다음부터 문자열 끝까지의 길이와 해당하는 문자열 개수를 키-값으로 가짐
     • isEnd: 문자열의 마지막 문자인지 여부를 boolean 형태로 저장.
2. class Trie 구현
   • 프로퍼티
     • root : 루트 노드. 비어 있는 상태
     • length_count: 트라이 객체에 저장된 문자열들의 길이에 따른 개수를 딕셔너리 형태로 저장. 문자열의 길이와 해당하는 문자열 개수를 키-값으로 저장
   • 메소드
     • insert_length_count(self, length): length 길이의 문자열에 따라 트라이 객체에 해당 길이의 문자열이 저장된 개수를 저장 및 갱신.
     • insert(self, word): 새로운 문자열 word를 트라이 객체에 추가.
     • count_by_length(self, word): word의 길이에 따라 트라이 객체에 몇개 저장되어 있는지 반환.
     • count_starts_with(self, prefix, length): 트라이 객체에 prefix로 시작하면서 그 뒤의 길이가 length인 문자열이 몇개 저장되어 있는지 반환
3. solution(words, queries) 구현
   1. 일반적인 문자열을 저장할 트라이 인스턴스 trie와, 순서를 뒤집은 문자열을 저장할 트라이 인스턴스 reverse_trie를 생성한다.
   2. words에 저장된 단어(word)를 순회하면서, 각각 trie와 reverse_trie에 추가해준다.
   3. 키워드별로 매치된 단어 개수를 저장할 리스트 answer를 생성한다.
   4. queries에 저장된 검색 키워드(query)를 순회하면서 아래와 같이 조건에 따라 answer에 값을 추가한다.
      1. 키워드의 첫 글자와 끝 글자가 모두 "?"인 경우, 문제 조건에 의해 모두 와일드카드 문자로 구성된 검색 키워드이므로, 단순히 trie.count_by_length(len(query))를 구한다.
      2. 키워드의 끝 글자가 "?"인 경우, 와일드카드가 접미사로 쓰인 검색키워드이므로, 와일드카드를 제외한 접두사를 구해 trie.count_starts_with(접두사, 남은 길이)를 구한다.
      3. 키워드의 첫 글자가 "?"인 경우, 와일드카드가 접두사로 쓰인 검색키워드이므로, 와일드카드를 제외한 접미사를 구해 reverse_trie.count_starts_with(접미사, 남은 길이)를 구한다.
   5. queries의 모든 요소에 대한 탐색이 종료되면 answer를 반환한다.

 

📌 시도 회차 수정 사항

1회차

효율성 테스트에서 시간 초과도 아니고 실패가 떠서 그 이유를 몰라서 답답했는데, 질문글에서 효율성 3번은 "?????"와 같이 검색 키워드가 모두 와일드카드 문자인 경우를 살펴보는 예제라고 알려줘서 겨우 문제를 해결했다. 한참을 헤맨 것 치고는 아주아주 사소한 실수였다^_ㅜ

 

나는 검색 키워드가 모두 와일드카드 문자인 경우를 처리하기 위해서, 트라이 객체에 length_count라는 딕셔너리 프로퍼티를 만들어줬었다. 그리고 새로운 문자열을 저장할 때 그 문자열의 길이를 키로 가진 값에 1을 더해주는 식으로 처리를 해서 나중에 트라이 인스턴스에 저장된 문자열 중 특정 길이의 문자열이 몇개인지 쉽게 구할 수 있도록 했다.

그런데 이렇게 문자열을 트라이에 저장할 때, word의 길이가 아니라 word 그 자체를 인수로 넘겨줬고.. 

그 결과 length_count 딕셔너리의 키가 문자열의 길이가 아닌, word로 저장되어 있었다🫠

 

결과적으로 insert_length_count 메소드에 word가 아니라 len(word)가 전달되도록 고쳐주었더니 무사히 통과했다. 지금와서 생각해보면 굳이 insert_length_count 메소드를 따로 두지 않고, insert 메소드 안에서 Trie 객체의 length_count를 갱신해줘도 되지 않을까..싶긴하다.

 

📌 정답 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.length_count = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.length_count = {}
    
    def insert_length_count(self, length):
        length_count = self.length_count
        self.length_count[length] = self.length_count.get(length, 0) + 1
        
    def insert(self, word):
        node = self.root  
        word_length = len(word)
        
        for i in range(word_length):
            char = word[i]
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            
            length = word_length-i-1
            length_count = node.length_count
            length_count[length] = length_count.get(length, 0) + 1
            
        node.isEnd = True
        
    def count_by_length(self, word):
        return self.length_count.get(word, 0)
    
    def count_starts_with(self, prefix, length):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.length_count.get(length, 0)

    
def solution(words, queries):
    trie = Trie()
    reverse_trie = Trie()
    
    for word in words:
        trie.insert(word)
        reverse_trie.insert(word[::-1])
        trie.insert_length_count(len(word))
    
    answer = []
    for query in queries:
        word_len = len(query)
        if query[0] == query[-1] == "?":
            answer.append(trie.count_by_length(word_len))
        elif query[-1] == "?":
            query = query.rstrip("?")
            answer.append(trie.count_starts_with(query, word_len-len(query)))
        else:
            query = query.lstrip("?")
            answer.append(reverse_trie.count_starts_with(query[::-1], word_len-len(query)))
    return answer