가사 검색

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

프로그래머스

---

1차 시도

query가 맨 앞이 "?"인지 확인하여 시작위치를 파악하고, query 길이와 word 길이가 같은지, "?"를 제외한 문자열이 word이 시작위치 기준으로 문자열 길이만큼 동일한지 확인하면 된다고 생각했습니다.

def solution(words, queries):
    answer = []
    
    for query in queries:
        cnt = 0
        N = len(query)
        if query[0] == "?":
            front = False
        else:
            front = True
        for word in words:
            if N != len(word):
                continue
            search_word = query.replace("?", "")
            search_N = len(search_word)
            if front:
                if word[:search_N] == search_word:
                    cnt += 1
            else:
                if word[-search_N:] == search_word:
                    cnt += 1
        answer.append(cnt)
    return answer

정확성: 25.0

효율성: 30.0

합계: 55.0 / 100.0

 

2차 시도

1차 시도보다 시간 효율성을 좋게하기 위해 딕셔너리를 생각했습니다.

딕셔너리 키는 word에 들어갈 수 있는 모든 query의 수이고, 값은 해당 쿼리로 검색할 수 있는 word의 수입니다.

def solution(words, queries):
    answer = []
    
    word_dict = {}
    
    for word in words:
        string = ""
        N = len(word)
        for token in word[:-1]:
            string += token
            keyword = string.ljust(N, "?")
            if keyword in word_dict:
                word_dict[keyword] += 1
            else:
                word_dict[keyword] = 1
        string = ""
        for token in word[::-1][:-1]:
            string += token
            keyword = string.ljust(N, "?")[::-1]
            if keyword in word_dict:
                word_dict[keyword] += 1
            else:
                word_dict[keyword] = 1
    
    for query in queries:
        answer.append(word_dict[query] if query in word_dict else 0)
    
    return answer

정확성: 25.0

효율성: 30.0

합계: 55.0 / 100.0

 

3차 시도

마지막으로 트리에 알고리즘을 적용했습니다.

class Node(object):
    def __init__(self, key = None):
        self.key = key
        self.length = []
        self.child = {}

class Trie():
    def __init__(self):
        self.head = Node()
        
    def insertTree(self, word):
        cur = self.head
        word_length = len(word)
        cur.length.append(word_length)
        for token in word:
            if token not in cur.child:
                cur.child[token] = Node(token)
            cur = cur.child[token]
            cur.length.append(word_length)
            
    def searchTree(self, word):
        cur = self.head
        word_length = len(word)
        for token in word:
            if token == "?":
                return cur.length.count(word_length)
            elif token not in cur.child:
                break
            cur = cur.child[token]
        return 0

def solution(words, queries):
    answer = []
    tree = Trie()
    reverse_tree = Trie()
    for word in words:
        tree.insertTree(word)
        reverse_tree.insertTree(word[::-1])
    for query in queries:
        if query[0] == "?":
            answer.append(reverse_tree.searchTree(query[::-1]))
        else:
            answer.append(tree.searchTree(query))
    return answer

정확성: 25.0

효율성: 75.0

합계: 100.0 / 100.0

 

코드 설명

Node class는 문자열의 token를 key로 갖고, 해당 노드를 거치는 word들의 길이를 나타내는 리스트를 length로 갖고, 자식노드를 나타내는 딕셔너리를 child로 갖습니다.

Trie class는 트리에 알고리즘을 적용시키기 위한 클래스입니다.

insertTree는  word의 token들을 노드에 차례로 넣고 함께 그 노드를 거치는 word들의 길이를 length 리스트에 넣어줍니다.

searchTree는 query의 token이 "?"가 나올 때까지 들어가서 "?"를 만나면 전 노드의 length에 찾고자하는 query 길이를 카운트하고 그 카운터 값을 리턴합니다.

solution function에서 "????o"와 같이 뒤에서 부터 검색하기 위한 reverse_tree를 따로 만들어 줍니다.

그리고 words에 대하여 모든 tree와 reverse_tree를 만듭니다.

그리고 queries에 대하여 query가 "?"로 시작하면 revers_tree에서 찾고 아니라면 tree에서 찾아서 answer 리스트에 추가합니다.