프로그래머스 - 가사 검색 (풀이중)

프로그래머스 링크

카카오 해설

문자열을 트리로 저장하는 트라이(Trie) 구성

카카오 해설을 참고하여

1. 와일드카드('?') 로 시작하는 쿼리를 뒤집어서 정방향처럼 탐색하기 위해 "정방향 Trie", "역방향 Trie" 를 각각 구성

2. 각 노드에 "count" 변수를 넣어서, 탐색 결과 반환이 용이하게 함

3. word의 길이에 따라 서로 다른 Trie에 저장함

 

세 가지를 따라했는데, 효율성 3번에서만 계속 timeout이 발생하는 중

 

해당 문제 질문 게시판에 입력 query가 전부 와일드카드("?????")인 경우도 고려하라고 하는데, 그걸 처리했는데도 여전히 틀림

 

소스코드는 아래에 (효율성3만 틀림)

class Node(object) :
    def __init__(self, char) :
        self.char = char
        self.count = 0
        self.children = {}
 
class Trie(object) :
    def __init__(self) :
        self.head = Node(None)
        self.allCount = 0 # 입력되는 word 갯수를 저장
 
    def insert(self, string) :
        currentNode = self.head
 
        for char in string :
            if char not in currentNode.children :
                currentNode.children[char] = Node(char)
                # 노드가 없으면 생성
 
            currentNode = currentNode.children[char] # 해당 알파벳의 노드로 이동
            currentNode.count += 1 # 입력되는 word의 갯수를 +1
            self.allCount += 1
 
    def startsWith(self, string) :
        currentNode = self.head 
 
        if string.count('?') == len(string) :
            # 입력이 모두 와일드카드인 경우
            return self.allCount # 해당 트리에 저장된 word 갯수를 모두 반환
 
        for char in string :
            if char == '?' : # 와일드카드가 발견되면
                break
            if char not in currentNode.children : # 하위 노드가 없으면
                return 0
            else :
                currentNode = currentNode.children[char]
        
        return currentNode.count
 
def solution(words, queries) :
    
    wordLength = set()
    for word in words :
        wordLength.add(len(word))
    
    normalTries = {}
    reversedTries = {}
    # word 길이 별로 따로 Trie를 생성
    # 정방향, 역방향 Trie 각각 생성
 
    for each in wordLength :
        normalTries[each] = Trie()
        reversedTries[each] = Trie()
 
    for word in words :
        normalTries[len(word)].insert(word)
        reversedTries[len(word)].insert(word[::-1])
        # 각 문자의 길이에 해당하는 Trie에 추가
 
    answer = []
    for query in queries :
        result = 0
        trieIdx = len(query)
 
        # 1. query 길이와 동일한 word자체가 없을 경우
        if len(query) not in wordLength :
            pass
        # 2. query 앞부분이 ? 인 경우
        elif query[0] == '?' :
            result = reversedTries[trieIdx].startsWith(query[::-1])
        # 3. query 뒷부분이 ? 인 경우
        else :
            result = normalTries[trieIdx].startsWith(query)    
 
        answer.append(result)
    
    return answer