[카카오 기출] 가사 검색

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

 

<처음 시도한 방법>

무식한 방법을 처음에 시도했다.

word = 'apple'이라면

딕셔너리의 키로

'?????', '?pple', '??ple', '???le', '????e', 'appl?', 'app??', 'ap???', 'a????' 을 만들어서 이 value값에 1을 추가해준다.

이 방법은 정확성은 통과되지만 효율성은 통과하지 못한다. 

import collections
def solution(words, queries):
    dct = collections.defaultdict(int)
    
    for word in words:
        temp = [x for x in word]
        temp2 = [x for x in word]
        for i in range(len(word)):
            new = temp
            new[i] = '?'
            trans1 = ''.join(new)
            
            new2 = temp2
            new2[-i-1] = '?'
            trans2 = ''.join(new2)
            
            dct[trans1] += 1
            dct[trans2] += 1
    
    answer = []
    for q in queries:
        answer.append(dct[q])
    return answer

 

<두번째 시도 방법 - 트라이 구현>

문자열 자료구조로 잘 알려진 트라이를 이용하여 문제를 풀었다.

기본적인 트라이의 뼈대는 아래에 미리 작성해두었던 코드를 빌렸다.

https://yiyj1030.tistory.com/322

[자료구조] 트라이(Trie) 구현 - 파이썬

 

약간 수정한 부분은 이 문제에선 startswith 메소드에서 몇개인지를 리턴해야 되기 때문에

Node클래스에 count 성분을 추가하고, 

Trie의 insert메소드 부분에 해당 node에 count를 더해주는 방식으로 구현하였다. 

이렇게 count를 추가한 방식이 제일 편한 것 같다. 원래는 bfs로 몇갠지 일일이 탐색하려 했지만.. 매우 귀찮..

class Node:
    def __init__(self):
        self.word = False
        self.count = 0                   ##  <========== 달라진 부분
        self.children = {}

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        node = self.root
        for char in word:     
            node.count += 1              ##  <========== 달라진 부분
            if char not in node.children:
                node.children[char] = Node()
            node = node.children[char]          
        node.word = True

    def startswith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0                 ##  <========== 달라진 부분
            node = node.children[char]
        return node.count                ##  <========== 달라진 부분


def solution(words, queries): 
    forward = {}
    backward = {}
    for i in range(1, 10**4 + 1):
        forward[i] = Trie()
        backward[i] = Trie()    
    
    for word in words:
        forward[len(word)].insert(word)
        backward[len(word)].insert(word[::-1])   
    
    answer = []
    for query in queries:
        if query[0] == '?' and query[-1] == '?':
            answer.append(forward[len(query)].root.count)
            continue
            
        if query[0]=='?':
            prefix = query.split('?')[-1][::-1]
            answer.append(backward[len(query)].startswith(prefix))
            continue
            
        if query[-1]=='?':
            prefix = query.split('?')[0]
            answer.append(forward[len(query)].startswith(prefix))
            continue 
    
    return answer