[프로그래머스] 가사 검색 / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/60060

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

---

<문제 설명>

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

words                                          queries                                       result

["frodo", "front", "frost", "frozen", "frame", "kakao"]

["fro??", "????o", "fr???", "fro???", "pro?"]

[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

 

<풀이법>

▒ 한줄 개념: Trie 알고리즘 ▒ 

Trie 알고리즘은 문자열 검색에 최적화된 알고리즘입니다. 

제가 쓴 글은 아니지만 아래의 글을 통해 트라이가 어떤 알고리즘이고, 어떤식으로 사용하는지 확인할 수 있습니다.

twpower.github.io/187-trie-concept-and-basic-problem

[Algorithm] 트라이(Trie) 개념과 기본 문제

문제에서 query는 '?'로 끝나는 경우, '?'로 시작하는 경우, '?'로만 이루어져 있는 경우의 3가지 경우가 있습니다.

따라서 이 3가지 경우에 따라 조건을 나눠서 구현해준다면, 효율성 테스트에도 문제없이 통과할 수 있습니다.

 

자세한 문제풀이에서 핵심은 다음과 같습니다.

 

1. 주어진 word를 이용한 trie{}
2. word를 거꾸로 뒤집어 이용한 rev_trie{}
3. 모든 단어의 길이를 센 counted[]

위에서 먼저 말한 3가지 경우를 위해 3가지 변수를 각각 사용합니다. 그 이유는 재귀 탐색의 효율성을 위해 '?'가 나오는 순간 바로 처리를 할 수 있도록 해야하기 때문입니다.

a. '?'로 끝나는 경우(ex:'fr???') : 가장 기본적인 형태입니다. 기본 trie{}를 이용하여 '?'가 나올 때까지 재귀탐색하면 됩니다.

b. '?'로 시작하는 경우(ex:'????o') : 모든 단어를 뒤집어 만든 rev_trie{}와, query 또한 뒤집어서 사용합니다. 반대로 탐색을 한다는 것 외에는 a 조건과 동일합니다. 

c. '?'로만 이루어진 경우 : counted 배열을 이용해서 단순히 길이가 같은 단어들의 갯수를 answer에 삽입합니다. 길이가 같은 모든 단어가 전부 답이 될 수 있기 때문입니다.

 

주의사항 1. '?'가 나타났을 때 남아있는 트라이의 모든 단어노드를 확인하기 위해서, 트라이의 노드마다 남아있는 단어노드의 갯수를 기록해야합니다. 그래야 남아있는 모든 노드를 체크하지 않고 한번에 정답을 얻어낼 수 있습니다.

 

주의사항 2. 파이썬에서 효율성 테스트 4,5 가 런타임 에러로 뜨는 경우가 있는데, 이는 프로그래머스에서 설정해둔 최대 재귀의 깊이가 1000이기 때문입니다. 따라서 다음의 코드를 사용해주면, 효율성 테스트도 끝까지 통과할 수 있습니다.

import sys
sys.setrecursionlimit(100001)

 

 

<코드(Python)>

import sys
sys.setrecursionlimit(100001)
def solution(words, queries):
    answer = []
    
    rev_words, counted = [], []   # 조건 b, c를 위한 두 변수
    for w in words:
        rev_words.append(w[::-1])
        counted.append(len(w))

    trie = make_trie({}, words)   # 조건 a 의 trie
    rev_trie = make_trie({}, rev_words)   # 조건 b 의 rev_trie 

    for query in queries:  # 3가지 조건으로 나누어서,
        if query[0] == '?' and query[-1] == '?':
            answer.append(counted.count(len(query)))
        elif query[0] == '?':
            answer.append(search_trie(rev_trie, query[::-1], len(query)))
        elif query[-1] == '?':
            answer.append(search_trie(trie, query, len(query)))

    return answer


def make_trie(trie, words):
    for word in words:
        cur = trie
        l = len(word)
        for w in word:
            if w in cur:
                cur = cur[w]
                cur['!'].append(l)
            else:
                cur[w] = {}
                cur = cur[w]
                cur['!'] = [l]
    return trie


def search_trie(trie, query, length):
    count = 0
    if query[0] == '?':
        return trie['!'].count(length)
    elif query[0] in trie:
        count += search_trie(trie[query[0]], query[1:], length)

    return count

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest