2020 KAKAO BLIND RECRUITMENT - 가사 검색 (파이썬)

1. 문제

- 카카오 코딩테스트 가사검색 문제

- 주어진 queries 에 맞는 words의 수를 리턴하는 문제

- 단 와일드카드 "?" 가 들어감

- queriesquequeriesries

2. 풀이 

- word와 query의 길이는 각각 100,000 이기 때문에 Brute Force로 풀면 시간초과가 나온다. 

- 따라서 시간초과가 떴고 써 본적이 없는 트라이 구조를 검색해서 적용해봤다.

- 와일드카드가 단어 중간에 들어갈 수 없으며 빈칸일 수는 없다는 점(와일드카드에 따라 단어 수가 변동되지 않는다는 점)이 힌트인듯

- 단어 길이는 최대 10,000 이기 때문에 각 단어길이에 맞는 Trie 배열을 생성해준다.(접두사가 같더라도 단어 길이에 따라 = 뒤에 붙는 와일드카드 ? 개수에 따라 답이 다르기 때문) 

- 접미사 처리를 위해 단어를 뒤집어준다. 

 

3. 배경지식- 트라이 자료구조

트라이 자료구조

→ 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

• 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때, 공간복잡도는 O(M*L)이고 시간복잡도: O(L)
• 트라이의 치명적 단점은 공간 복잡도 따라서 자료 수가 적을 때 사용하는 것이 유리 
• 단어의 길이가 짧고, 파생되는 child 수가 작아야 함(알파벳, 숫자 등)
• Prefix tree 라고도 하는데 문자열을 검색할 때 주로 쓰임

4. 코드

class Node:
    def __init__(self):
        self.dic = {}
        self.count = 0
# 각 노드에서 파생되는 단어 수를 계산하기 위해 count 변수 사용 

class Trie:
    def __init__(self):
        self.root = Node()
        
    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.dic:
                cur.dic[c] = Node()
            cur = cur.dic[c]
            cur.count += 1
# 각 단어의 알파벳을 차례로 순환하고 알파벳 c를 키로하는 자식노드가 없다면 만들어 준다.(count를 쌓아준다)
# cur를 children 노드로 옮겨줘서 단어 끝까지 진행

    def search(self, query):
        cnt = 0
        if query == '':
            for children in self.root.dic.values():
                cnt += children.count
            return cnt
      	# 함수 인자로 받는 query는 prefix은데 빈칸이라는 뜻은 전부 와일드 카드 "?"로 이루어졌다는 것
        # 따라서 root노드 자식노드들의 count를 모두 더해 리턴해준다(길이가 같은 단어들 모두 리턴)
        cur = self.root
        for c in query:
            if c not in cur.dic:
                return 0
            cur = cur.dic[c]
        cnt = cur.count
        return cnt
        # prefix의 마지막 알파벳의 count를 리턴하는데 마지막 단어에서 파생되는 단어들의 수의 합이기 때문
        # 물론 마지막 알파벳까지 가지 전에 알파벳을 키로하는 자식노드가 없다면 0 리턴 
    
def solution(words, queries):
    trie = [Trie() for i in range(10001)]
    reverse = [Trie() for i in range(10001)]
    # 단어의 길이의 수인 1~10,000 마다의 트라이 생성, 접미사 처리를 위해 reverse도 생성
    # 길이를 배열 index로 쓰기위해 range(10001)로 편의상 사용
    for word in words:
        trie[len(word)].insert(word)
        reverse[len(word)].insert(word[::-1])
    answer = []
    for query in queries:
        L = len(query)
        if query[0] != '?':
            prefix = query.split('?')[0]
            answer.append(trie[L].search(prefix))
        else: 
            prefix = query[::-1].split('?')[0]
            answer.append(reverse[L].search(prefix))
    return answer

- 트라이 자료구조를 코드로 구현한적 없는 상태에서 풀었으므로 초보자는 이해하기 쉬운 코드인 반면 허접할 수 있음