[Seop's의 코드풀이] 프로그래머스 가사 검색 - Python

programmers.co.kr/learn/courses/30/lessons/60060#

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

 

 

 

문제 개요

이번에 풀어볼 문제는 2020 Kakao 블라인드 채용에 출제되었던 가사 검색이란 문제입니다.  

queries에 있는 '?'가 섞인 문자열이 있는데 각 해당하는 문자열이 words에 있는 것과 몇개나 매칭이 되는지 알아봐야 합니다. 

단순하게 모든 문자열을 비교한다면 풀릴 것 같은 문제입니다. 하지만 그렇게 한다면 시간은 굉장히 오래걸리게 됩니다.

 

문제 풀이 IDEA

문자열들이 있는 집합에서 특정 문자열을 효율적으로 검색하기 위해서 Trie 라는 자료구조를 사용 할 것 입니다.  

Trie 에 대한 설명은 다음 링크에 있습니다.  설명보기

 

queries 에 있는 문자열은 모두 "?"를 앞이나 뒤에 가지고 있습니다. 이는 문자열의 접두,접미사를 확인하고 물음표가 

나온 이후에는 길이만 맞다면 매칭이 된 것입니다.  

접두사, 접미사를 활용할 것이기 때문에 우리는 2가지 종류의 Trie 구조가 필요합니다.

문자열의 길이 또한 일치해야하기 때문에 길이에 따른 Trie가 필요합니다. 

즉 길이에 따른 Trie 안에 2가지 종류의 Trie를 만들 것입니다. 

보다 쉬운 이해를 위해 길이가 5인 문자열의 Front, Rear Trie를 만들어 보면 다음과 같습니다.(문제 예시 사용)

 

 

 

위 그림처럼 모든 길이의 Trie에 2가지 종류의 Trie 트리를 만들면 길이에 따른 접두,접미사 이후의 단어들의 개수를

빠르게 구해 낼 수 있습니다. 

 

Code

질문과 피드백은 언제나 감사드립니다.

class Node :
    def __init__(self, data) :
        self.data = data
        self.child = dict()
        self.cnt = 0
class Trie :
    def __init__(self) :
        self.front = Node("")
        self.rear = Node("")
    
    def makeFrontTrie(self, word) :
        self.front.cnt += 1
        if word[0] not in self.front.child :
            self.front.child[word[0]] = Node(word[0])
        target = self.front.child[word[0]]
        target.cnt += 1
        for i in range(1, len(word)) :
            if word[i] not in target.child :
                target.child[word[i]] = Node(word[i])
            target = target.child[word[i]]
            target.cnt += 1
    
    def makeRearTrie(self, word) : 
        self.rear.cnt += 1
        word = word[::-1]
        if word[0] not in self.rear.child :
            self.rear.child[word[0]] = Node(word[0])
        target = self.rear.child[word[0]]
        target.cnt += 1
        for i in range(1, len(word)) :
            if word[i] not in target.child :
                target.child[word[i]] = Node(word[i])
            target = target.child[word[i]]
            target.cnt += 1
    
    def getAnswer(self, quer) :
        if quer[0] == "?" :
            quer = quer[::-1]
            flag = True    
        else : 
            flag = False    

        if flag : 
            target = self.rear
        else :
            target = self.front
        
        for i, v in enumerate(quer) :
            if v == "?" :
                if i == 0 :
                    if flag :
                        return self.rear.cnt
                    else :
                        return self.front.cnt
                return target.cnt
            if v in target.child :
                target = target.child[v]
            else :
                return 0


def solution(words, queries):
    trieDict = dict()
    answer = []
    for i in words :
        if len(i) not in trieDict :
            trieDict[len(i)] = Trie()
        trieDict[len(i)].makeFrontTrie(i)
        trieDict[len(i)].makeRearTrie(i)
    for i in queries :
        if len(i) in trieDict :
            answer.append(trieDict[len(i)].getAnswer(i))
        else :
            answer.append(0)
    

    return answer