카카오블라인드/2020/가사검색

프로그래머스 이용 : https://programmers.co.kr/learn/courses/30/lessons/60060

 

처음에 for문 2개로 풀었더니 효율성 1,2,3번을 통과하지 못한다. 하위 소스가 그 내용이다.

def solution(words, queries):
    result = []
    """
    queries 총 문자 개수, 맞춰야하는 문자 개수
    맞으면 ans += 1
    """
    for q in queries:
        ans = 0
        total_len = len(q)
        key = q.replace("?","")
        key_idx = q.find(key)
        for word in words:
            if len(word) != total_len:
                continue
            if key == "":
                ans+=1
                continue
            idx = word.find(key, key_idx)
            if idx == key_idx:
                ans+=1
        result.append(ans)
                
    return result

여기서 앞서 배웠던 hash를 사용하여 다시 풀어보았다.

python에서 hash는 dict를 사용한다. 다음 소스는 효율성 2번 케이스 제외하고는 통과하였다.

def solution(words, queries):
    """
    queries 총 문자 개수, 맞춰야하는 문자 개수
    맞으면 ans += 1
    """
    result = {}
    for q in set(queries):
        result[q] = 0
        total_len = len(q)
        key = q.replace("?", "")
        for word in words:
            if len(word) != total_len:
                continue
            if key == "":
                result[q] += 1
                continue
            key_idx = q.find(key)
            idx = word.find(key, key_idx)
            if idx == key_idx:
                result[q] += 1

    return [result[q] for q in queries]

결국은 Trie 자료구조를 사용해야 풀 수 있는 문제였다.

 

Trie

사용 : 검색어 자동완성, 사전에서 찾기, 문자열 검사

시간복잡도 :

• 제일 긴 문자열의 길이(L), 총 문자열들의 수(M)
• 생성시 시간복잡도 : O(M*L), 모든 문자열들을 넣어야하니 M개에 대해서 Trie 자료구조에 넣는건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서 O(M*L)만큼 걸린다.
• 탐색시 시간복잡도 : O(L), 트리를 타고 들어가봤자 가장 긴 문자열의 길이만큼만 탐색하기 때문에 O(L)만큼 걸린다.

wiki