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

티스토리 메뉴 펼치기 댓글수0

프로그래밍/기타

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

snoopybox
댓글수0

문제 :

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


나의 풀이 :

def solution(wordsqueries):
    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 발생한다.

맨위로

https://www.snoopybox.co.kr/2054

신고하기