2020 KAKAO RECRUITMENT - 가사검색

🔗 2020 KAKAO RECRUITMENT - 가사검색 

📌오늘의 학습 키워드

• Trie

✨공부한 내용 본인의 언어로 정리하기

• 삼중 for문으로 쓰고 당연히 효율성 테스트에서 걸릴 것을 예상했다.
• 질문하기를 좀 뒤져봤는데 트라이(trie)라는 단어가 많이 떠서 공부했다. 
• Trie는 문자열 검색 시 효율을 높이기 위해서 트리 구조를 사용하는 것으로 dictionary를 사용해 구현한다.   
  • 트라이를 적용해보려고 어제 공부한 다음에 자기 전에 생각해 보는데, 트리 구조를 사용하는 것까지는 이해를 했는데 단어의 길이를 어디서 알아내는지 모르겠었다. 
  • dictionary의 key 값으로 단어의 길이를 사용하며 단어의 길이로 1차 검색 이후 트리를 타고 내려간다. 

📚오늘의 회고

1. 첫번째로는 삼중 for문을 사용해 해결하려고 했다. 정확도에서는 맞았지만 효율성에서 시간초과가 나왔다. 
2. 문제 중에서 '?'가 접미사 또는 접두사로만 들어간다고 하여, 이를 반영해 보았다. 마찬가지로 정확도에서는 맞았지만 시간초과가 나왔다. 
3. Trie를 적용해서 풀이해 보았으나 효율성 테스트 3번에서 계속 틀렸다고 떴다.
4. '???'와 같이 전체가 와일드카드인 경우에 제대로 처리하지 않아 문제가 생겨서 고쳐줬다. 

print(solution(["spd","asd","sdf"], ["???"])) #3

 

[🤓문제 해결 코드]

class TrieNode:
    def __init__(self):
        self.count = 0
        self.childern = {}


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

    def insert(self, word):
        node = self.root
        for w in word:
            if w not in node.childern:
                node.childern[w] = TrieNode()
            node = node.childern[w]
            node.count += 1

    def search(self, query):
        node = self.root
        for q in query:
            if q == '?':
                return node.count
            if q not in node.childern:
                return 0
            node = node.childern[q]
        return node.count


def solution(words, queries):
    trie = {}
    reversed_trie = {}
    answer = []

    # trie 초기화
    for word in words:
        length = len(word)
        if length not in trie:
            trie[length] = Trie()
            reversed_trie[length] = Trie()
        trie[length].insert(word)
        reversed_trie[length].insert(word[::-1])

    for query in queries:
        length = len(query)

        if length not in trie:
            answer.append(0)
            continue

        # 전체가 와일드 카드인 경우 처리
        if query[-1] == '?' and query[0] == '?':
            total = 0
            for i in trie[length].root.childern.values():
                total += i.count
            answer.append(total)
            continue

        # 접두사인 경우 reversed 적용
        if query[0] == '?':
            result = reversed_trie[length].search(query[::-1])
        else:
            result = trie[length].search(query)
        answer.append(result)

    return answer

 

print(solution(["pi", "frodo", "front", "frost", "frozen", "frame", "kakao"],
               ["fro??", "????o", "fr???", "fro???", "pro?", "??"]))
#[3, 2, 4, 1, 0, 1]

print(solution(["spd","asd","sdf"], ["???"]))
#[3]