[Programmers] Level 4. 가사 검색

🔗 Problem Link

프로그래머스

---

❔Thinking

• 한 글자를 의미하는 '?'를 포함하는 쿼리가 여러개 주어질 때, 각 쿼리가 words의 몇 단어와 매치되는지를 반환한다.

---

💻Solution

1. 이진탐색을 활용한 풀이

from bisect import bisect_left, bisect_right

def solution(words, queries):
    answer = []
    word_list = [[] for _ in range(100001)]
    word_list_reversed = [[] for _ in range(100001)]
    # 길이 별 단어 리스트
    for word in words:
        word_list[len(word)].append(word)
        word_list_reversed[len(word)].append(word[::-1])
        
    # 길이 별 단어 리스트 정렬
    for i in range(100001):
        word_list[i].sort()
        word_list_reversed[i].sort()
    
    # 쿼리 확인
    for q in queries:
        if q[0] != '?': # 시작 알파벳이 정해진 경우
            query_from_a = q.replace('?', 'a')
            query_to_z = q.replace('?', 'z')
            cnt = bisect_right(word_list[len(q)], query_to_z) - bisect_left(word_list[len(q)], query_from_a)
            answer.append(cnt)
        else: # ?로 시작하는 경우
            q = q[::-1]
            query_from_a = q.replace('?', 'a')
            query_to_z = q.replace('?', 'z')
            cnt = bisect_right(word_list_reversed[len(q)], query_to_z) - bisect_left(word_list_reversed[len(q)], query_from_a)
            answer.append(cnt)
    return answer

 

2. 트라이(Trie) 자료구조를 활용한 풀이

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

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

    def insert(self, string):
        cur_node = self.head
        n = len(string)
        cur_node.len.append(n)
        for char in string:
            if char not in cur_node.child:
                cur_node.child[char] = Node(char)
            cur_node = cur_node.child[char]
            cur_node.len.append(n)
        cur_node.len.append(n)
        cur_node.data = string

    def search(self, string, n):
        cur_node = self.head
        if string == '':
            return cur_node.len.count(n)
        for char in string:
            if char not in cur_node.child:
                return False
            cur_node = cur_node.child[char]
        if cur_node.data or n in cur_node.len:
            return cur_node.len.count(n)
        return False

def solution(words, queries):
    t = Trie()
    t_reversed = Trie()
    answer = []
    for w in words:
        t.insert(w)
        t_reversed.insert(w[::-1])
    for q in queries:
        q_replaced = q.replace('?', '')
        if q_replaced == '':
            answer.append(t.search(q_replaced, len(q)))
            continue
        elif q[0] == '?':
            tmp = t_reversed.search(q_replaced[::-1], len(q))
        elif q[-1] == '?':
            tmp = t.search(q_replaced, len(q))
        if tmp > 0:
            answer.append(tmp)
        else:
            answer.append(0)
    return answer

---

🗝️keypoint

1. 와일드카드인 '?'가 문자열 중간에 등장한다면 정확한 답을 얻을 수 없다.
2. '?'가 임의의 글자 하나를 의미하기 때문에, a부터 z까지 모두 대입해볼 수 있다.
3. Trie구조를 활용할 경우, '?'를 제외한 나머지 문자열과 해당 문자열을 접두어로 하는 단어의 길이를 확인한다.