[프로그래머스] 가사 검색 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60060

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

 

문제의 설명은 어렵지 않았다.

처음에는 word에 ?를 하나씩 붙여서 가능한 경우를 다 만들고 그것을 키로하고 값은 개수로 하는 딕셔너리로 만들었었다. 그리고 쿼리문을 키로해서 딕셔너리를 확인했다.

word의 길이는 최대 10000자이고, 모든 가사의 길이의 합이 1백만자 이하 이므로 되지 않을까 했다.

근데 문자를 이어붙이는 과정에서 슬라이싱이 많이 들어가서 효율성 테스트에서 틀리지 않았나 싶다.

 

그래서 해설을 봐보니 트라이 자료구조를 사용해야한다고 한다.

문자열을 트리 구조로 저장해서 단순 비교해서 검색하는 경우 훨씬 빠르다고 한다.

 

트라이 자료구조에 대해서는 다른 블로그를 참고했다.

https://velog.io/@gojaegaebal/210126-개발일지50일차-트라이Trie-알고리즘-개념-및-파이썬에서-구현하기feat.-Class

210126 개발일지(50일차) - 트라이(Trie) 알고리즘 개념 및 파이썬에서 구현하기(feat. Class)

 

 

문제를 풀기 위해서는 가장 먼저 문자열을 트라이 자료구조로 변환해야한다.

각 노드들은 child와 length를 갖도록 했다. 맨처음 트라이의 헤드는 빈껍데기다. 여기에 값들이 추가 된다.

child는 다음 노드들을 저장할 딕셔너리고 length는 해당 노드까지 접근한 문자열의 길이를 저장한다.

만약 frodo라면 f,r,o,d,o 각각에 length[5]는 1의 값이 될 것이다.

 

이것은 쿼리문을 검색 할 때 사용한다.

만약 쿼리문이 fro??라고 왔다고 해보자.

 

처음 헤드의 자식에서 f를 찾고 f로 이동한다.

f에서 r을 찾고 r로 이동한다.

r에서 o를 찾고 o로 이동한다.

o에서 ?를 찾을 차례이다. 근데 ?는 아무거나 와도 되는 와일드카드이고 이 이후로 문자는 모두 ? 문자이다.

따라서 다음을 확인할 필요가 없다. 그렇기 때문에 현재 노드까지 들어온 문자중 길이가 쿼리문과 똑같은 단어의 개수를 반환 해주면된다. 이때 이값은 length에 저장되어 있다.

 

주의할 점은 와일드 카드가 왼쪽,오른쪽 한쪽에만 오던지 아니면 모두 와일드카드이다.

왼쪽, 오른쪽을 확인하기 위해 트라이를 두개를 만들어줘야한다.

오른쪽이 와일드 카드인 것은 변환없이 그대로 구현하면 된다.

그치만 왼쪽이 와일드 카드인 경우 단어를 뒤집어야한다. 왜나면 내가 구현한 알고리즘은 쿼리 검색시 ? 문자까지만 보고 나오기 때문이다. 마찬가지고 쿼리문도 뒤집어서 검색해줘야한다.

 

그리고 모두 와일드카드인것을 체크하기 위해 단어의 길이를 키로하는 딕셔너리를 만들어줬다.

 

from sys import setrecursionlimit
setrecursionlimit(100001)
def solution(words, queries):
    answer = []
    trie = make_trie(words, {'length': {}, 'child': {}})

    r_words = []
    all_wild = {}
    for word in words:
        r_words.append(word[::-1])
        length = len(word)
        if length in all_wild:
            all_wild[length] += 1
        else:
            all_wild[length] = 1
    r_trie = make_trie(r_words, {'length': {}, 'child': {}})

    for q in queries:
        if q[0] == q[-1] == '?':
            answer.append(all_wild.get(len(q),0))
        elif q[0] == '?':
            answer.append(search_trie(q[::-1],0,r_trie))
        else:
            answer.append(search_trie(q,0,trie))
    return answer


def make_trie(words, trie):
    for word in words:
        cur = trie

        length = len(word)
        for w in word:
            if w in cur['child']:
                cur = cur['child'][w]
                if length in cur['length']:
                    cur['length'][length] += 1
                else:
                    cur['length'][length] = 1
            else:
                cur['child'][w] = {
                    'length': {
                        length: 1
                    },
                    'child': {}
                }
                cur = cur['child'][w]
    return trie
def search_trie(q,idx,trie):
    if q[idx] == '?':
        return trie['length'].get(len(q),0)
    else:
        if q[idx] in trie['child']:
            return search_trie(q,idx+1,trie['child'][q[idx]])
        else:
            return 0