220316 - 가사 검색

◾ 가사 검색 : 프로그래머스 LEVEL 4

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

문제

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.

그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

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

---

입력

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

---

◾ 풀이

1. 해설

• 트라이(Trie) 자료구조를 통해 검색을 빠르게 실행하도록 한다.
  • https://twpower.github.io/187-trie-concept-and-basic-problem
  • https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
• 트라이 구조를 조금 변형하여 각 위치에서 가능한 가사들의 길이도 추가로 저장한다.
• ?가 접미사 혹은 접두사이므로 총 3가지 경우가 가능하다.
  • ?로만 이루어진 경우 : 길이가 같은 경우
  • ?로 끝나는 경우 : ? 앞까지의 문자가 같은 경우
  • ?로 시작하는 경우 : 가사와 쿼리를 뒤집은 뒤 ? 앞까지의 문자가 같은 경우
• 가사와 뒤집은 가사를 각각 트라이 구조로 만들어 query에 따라 탐색한다.

---

2. 프로그램

1. rev_words, counted 초기화
   • rev_words : words의 각 요소를 뒤집은 리스트
   • counted : 각 길이의 문자 개수
2. 트라이 구조 생성
   • trie : 기본 words를 이용해 구성
   • rev_trie : rev_words를 이용해 구성
3. 각 query에 대해 탐색
   • ?에 따라 탐색 방법 선택
   • ?로만 이루어진 경우 : counted에서 해당 길이의 가사 확인
   • ?로 시작하는 경우 : rev_trie와 query[::-1]을 통해 탐색
   • ?로 끝나는 경우 : trie와 query를 통해 탐색

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

    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] == '?':
            len_q = len(query)
            if len_q in counted:
                answer.append(counted[len(query)])
            else:
                answer.append(0)
        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['len'].append(l)
            else:
                cur[w] = {}
                cur = cur[w]
                cur['len'] = [l]
    return trie

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

    return count