가사 검색

문제

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

접근 방식

• 초기: 딕셔너리 활용 (효율성 3/5)

word 별로 나올 수 있는 모든 조합을 딕셔너리에 저장했다.
다만 이렇게 하면 단어 하나당 나올 수 있는 경우의 수가 2*n - 1로 key 개수 자체가 매우 커지기 때문에 탐색이 오래 걸린다는 단점이 있다.

찾아보니 크게 두 가지 접근 방식이 가능하다고 한다.

1. Trie 활용
2. 이진 탐색 활용

👇 Trie의 기본적인 컨셉은 아래를 참고!
Trie란?

1. Trie 활용

내 풀이 (합계: 85.0 / 100.0, 효율성 4/5)

'?'은 접두사 혹은 접미사로 올 수 있기 때문에 front_trie, end_trie 따로 만들어줬다.

dfs는 단어 길이를 추적해서 돌아야 하기 때문에 depth 정보와 쿼리 길이도 함께 넘겼다.

import sys
sys.setrecursionlimit(100001)
from collections import defaultdict

def build_trie(words, trie):
    for word in words:
        cur_root = trie
        for c in word:
            if not c in cur_root:
                cur_root[c] = {}
            cur_root = cur_root[c]
        cur_root['*'] = word
    return trie

def dfs(cur_root, depth, res, qlen):
    if depth > qlen:
        return
    for k, v in cur_root.items():
        if k == '*':
            if depth == qlen:
                res.append(v)
            continue
        dfs(v, depth + 1, res, qlen)

def search_dfs(trie, query):
    root_dict = trie
    res = []
    depth = 0
    for c in query:
        if c != '?':
            if c not in root_dict:
                return []
            root_dict = root_dict[c]
            depth += 1
        else:
            dfs(root_dict, depth, res, len(query))
            break
    return res

def word_lengths(words):
    lengths = defaultdict(int)
    for word in words:
        lengths[len(word)] += 1
    return lengths

def solution2(words, queries):
    front_trie = build_trie(words, {})
    end_trie = build_trie(list(map(lambda word: word[::-1], words)), {})
    lengths = word_lengths(words)
    res = []
    for query in queries:
        if query.count('?') == len(query): #전부 다 ?인 경우
            res.append(lengths[len(query)])
        else:
            c = 0
            if query[0] == '?':
                c = search_dfs(end_trie, query[::-1])
            else:
                c = search_dfs(front_trie, query)
            res.append(len(c))
    return res

다만 효율성 1번을 시간 초과로 통과 못했다..🥲

카카오 해설을 참고하니까 단어 길이에 따른 트라이를 만들 것을 추천하던데 생각해보니 주어진 모든 단어로 트라이 만들면 트라이를 쓰나마나 한 시간복잡도다. 최소 2에서 10000의 depth를 가지는 딕셔너리가 만들어지고 단어 개수가 최대 100000이라면 dfs로 탐색하는 시간 복잡도가 최악의 경우 O(N*M)(N: 단어 개수, M: 가장 긴 단어의 길이)로 1억을 넘어가기 때문이다.

2. 이진 탐색 활용

'?' 부분은 'a' ~ 'z'로 대체해서 해당 범위에 포함되는 문자열의 개수를 반환하면 간단하게 풀 수 있다

👇 count_by_range
정렬된배열에서특정수의개수구하기

내 풀이 (합계: 85.0 / 100.0, 효율성 4/5)

from bisect import bisect_left, bisect_right
from collections import defaultdict

def count_by_range(arr, l, r): #'?' 이전의 query 탐색 범위 지정
    left = bisect_left(arr, l)
    right = bisect_right(arr, r)
    return right - left

def make_dictionary(words):
    dictionary = defaultdict(list)
    for word in words:
        dictionary[len(word)].append(word)
    for k in dictionary.keys(): #사전순 정렬
        dictionary[k].sort()
    return dictionary
    
def solution(words, queries):
    #단어 길이 별 나누기
    word_dict = make_dictionary(words)
    word_dict_rev = make_dictionary(list(map(lambda word: word[::-1], words))) #역순
    res = []
    for query in queries:
        qlen = len(query)
        if qlen not in word_dict:
            res.append(0)
            continue
        if query.count('?') == qlen:
            res.append(word_dict[qlen])
            continue
        cnt = 0
        if query[0] == '?':
            search_lst = word_dict_rev[qlen]
            cnt = count_by_range(search_lst, query[::-1].replace('?', 'a'), query[::-1].replace('?', 'z'))
        else:
            search_lst = word_dict[qlen]
            cnt = count_by_range(search_lst, query.replace('?', 'a'), query.replace('?', 'z'))
        res.append(cnt)
    return res

이건.. 이건 효율성 3번 통과 못하는데 뭐가 문제일까🥲