프로그래머스 가사검색 파이썬 문제 풀이

문제 설명

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

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

 

문제풀이1 : 이진탐색, 실패

처음 내가 접근한 방법은 이진탐색으로 '?'의 위치를 빠르게 찾고, '?' 전후의 값만 빠르게 비교하는 것이었다. '?'의 위치를 빠르게 찾기 때문에 효율성도 괜찮을꺼라는 생각을 했는데, 효율성 테스트 중 1~3번 Test Case는 계속 시간초과가 발생했다. 

'?'의 위치를 빠르게 찾을 수 있는 것은 맞으나, 예를 들어 길이 10000의 문자가 '?'가 하나도 없는 경우만 나온다면, 사실상 완전탐색이나 다름이 없기 때문이다. 따라서, 시간 초과 할 수 밖에 없는 방법이었다.

 

문제풀이2 : Trie 구조 사용

아무리 생각해도 방법이 나오지 않아, 다른 분들의 풀이를 확인했다. 확인 시, Trie 자료구조를 사용하여서 쉽게 푸는 것을 확인했다. 이 문제를 풀면서 Trie 자료 구조를 사용했다. 문제를 푼 로직은 다음과 같다.

1. Node Class를 구현한다.

2. Trie Class를 구현한다.

3. 주어진 그대로 문자를 저장하는 Trie, 주어진 문자를 뒤집어 저장하는 Trie 두 가지를 저장할 수 있는 딕셔너리를 각각 10000개씩을 만든다.

4. Trie에 문자를 넣어주는데, 문자열의 길이에 따라 다른 Trie 구조에 넣는다.

5. Query 수행 시, '?'를 제거한 접미사, 접두사만 넣은 후 문자의 갯수를 센다. 접두사 일 경우, 문자열을 뒤집어서 뒤집어진 Trie에서 Count를 진행하고 접미사일 경우 그대로 Trie 구조에서 Count를 진행한다.

class Node(object) :
    def __init__(self,data):
        self.data = data
        self.count = 0
        self.child = {}

class Trie(object) :
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        cur = self.head
        cur.count +=1

        for c in string :
            if c not in cur.child :
                cur.child[c] = Node(c)
            cur = cur.child[c]
            cur.count += 1


    def count(self,prefix):
        cur = self.head

        for c in prefix :
            if c not in cur.child :
                return 0
            cur = cur.child[c]

        return cur.count



def make_tree(words,is_reversed = False) :
    my_dict = [[] for _ in range(10001)]
    for i in range(10001) :
        my_dict[i] = Trie()

    for word in words :
        if is_reversed == True :
            word = word[::-1]
        my_dict[len(word)].insert(word)
    return my_dict



def solution(words, queries):
    answer = []
    a_trie = make_tree(words)
    b_trie = make_tree(words,True)

    for query in queries :
        find_len = len(query)
        if query[0] != '?':
            query = query.replace('?','')
            answer.append(a_trie[find_len].count(query))
        else :
            query = query.replace('?','')
            answer.append(b_trie[find_len].count(query[::-1]))


    return answer