프로그래머스 가사 검색 (python, 파이썬)

• 문제 설명

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

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

---

• 코드

class 사용

from collections import defaultdict

class Node:
    def __init__(self, data):
        self.data = data
        self.cnt = 0
        self.children = {}
        
class Trie:
    def __init__(self):
        self.head = Node(None) # 초깃값 생성
        
    def insert(self, string):
        cur = self.head # head부터 시작
        cur.cnt += 1 # count 1추가 
        
        # 문자열 한 문자씩
        for s in string:
            # 자식에 해당 문자가 없다면
            if s not in cur.children:
                # 새로운 노드를 구성해서 넣어준다
                cur.children[s] = Node(s)
            # 다음 자식 문자로 현재 상태를 옮겨주고
            cur = cur.children[s]
            # 값을 1추가
            cur.cnt += 1
            
    def count(self, prefix):
        # head부터 시작
        cur = self.head
        
        # 접두사 문자열 문자 돌리기
        for s in prefix:
            # 자식에 문자가 없다면
            if s not in cur.children:
                # 0 return
                return 0
            # 현재 상태를 자식으로 옮겨준다
            cur = cur.children[s]
        
        # for문을 다 돌고나온 현재 상태의 cnt값을 return
        return cur.cnt

def make_trie(string, reverse):
    # 값이 없다면 0으로 초기화시키기 위해서 defaultdict사용
    trie_dic = defaultdict(Trie)
    
    # 문자열 돌리기
    for s in string:
        # 순서를 뒤집어야할 경우
        if reverse:
            s = s[::-1]
        
        # trie_dic의 처음 key는 문자열의 길이
        # 문자열의 길이를 하는 이유는 frodo, frodon이 있을때
        # fro??라는 query는 길이까지 계산해주어야하기 때문이다.
        trie_dic[len(s)].insert(s)
        
    return trie_dic

def count_word(trie, reverse_trie, query):
    # ? 제거
    new_query = query.replace('?', '')
    
    # ?로 시작된다면 역순으로 집어넣어준다
    # -> 역순으로 시작해야 처음부터 시작할때처럼 똑같은 조건으로 구해줄수있기 때문이다.
    # 처음 시작은 len(query) 문자열의 길이로 시작 이후 count함수를 통해 숫자 계산
    if query[0] == '?':
        return reverse_trie[len(query)].count(new_query[::-1])
    else:
        return trie[len(query)].count(new_query)
    
def solution(words, queries):
    answer = []
    
    trie = make_trie(words, False)
    reverse_trie = make_trie(words, True)
    for query in queries:
        temp = count_word(trie, reverse_trie, query)
        answer.append(temp)
    
    return answer

class 사용 x

def make_trie(words, reverse):
    dic = {}
    for word in words:
        dic.setdefault(len(word), {})
        current_dic = dic[len(word)]

        if reverse:
            word = word[::-1]

        for letter in word:
            current_dic.setdefault(letter, [0, {}])
            current_dic[letter][0] += 1
            current_dic = current_dic[letter][1]
            
    return dic

def count(query, new_query, cur_dic):
    if len(query) not in cur_dic.keys():
        return 0

    current_dic = cur_dic[len(query)]
    for letter in new_query:
        if letter not in current_dic.keys():
            return 0

        current_dic = current_dic[letter][1]
        
    return sum([v[0] for k, v in current_dic.items()])
    
def solution(words, queries):
    answer = []
    dic = make_trie(words, False)
    reverse_dic = make_trie(words, True)
    
    for query in queries:
        new_query = query.replace('?', '')
        if query[0] == '?':
            temp = count(query, new_query[::-1], reverse_dic)
            answer.append(temp)
        else:
            temp = count(query, new_query, dic)
            answer.append(temp)
        
    return answer

word의 최대 길이도 100,000이고 query의 최대 길이도 100,000이기떄문에 완전탐색으로 돌리면 시간초과가 날 수밖에 없기 때문에 기존에 겹치는 정보는 key로 담아주어 시간을 단축시켜주는 trie자료구조를 사용한다

---

• 출처

programmers.co.kr/learn/courses/30/lessons/60060?language=python3