[Python3][2020카카오공채] 가사 검색

문제 :

https://www.welcomekakao.com/learn/courses/30/lessons/60060

나의 풀이 :

def solution(words, queries):

    trie_by_length = [({}, {}) for _ in range(10001)]

    for word in words:

        length = len(word)

        t = trie_by_length[length][0]

        for c in word:

            t['count'] = t.get('count', 0) + 1

            t.setdefault(c, {})

            t = t[c]

        t = trie_by_length[length][1]

        for c in word[::-1]:

            t['count'] = t.get('count', 0) + 1

            t.setdefault(c, {})

            t = t[c]

    ans = []

    for query in queries:

        length = len(query)

        if query[0] == '?':

            t = trie_by_length[length][1]

            query = query[::-1]

        else:

            t = trie_by_length[length][0]

        for c in query:

            if c == '?':

                ans.append(t.get('count', 0))

                break

            if c not in t:

                ans.append(0)

                break

            t = t[c]

    return ans

한마디 :

정확성 테스트는 아무렇게나 풀어도 쉽게 통과 가능하지만, 효율성 테스트는 Trie를 활용하지 않으면 2개 TC에서 Timeout 발생한다.