[프로그래머스] 2020 Kakao Blind Recuritment : 가사 검색

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

프로그래머스

📄 문제개요

• 검색 할 대상이 되는 문자열이 주어지고, 쿼리가 주어진다.
• 해당 쿼리를 검색 할 대상에서 매칭되는 개수를 카운팅하여 결과를 출력한다.
• 예를들어 for??의 쿼리가 주어지면 [frodo, front, forst] 에 매칭이 되어 3값일 출력해야한다.

🤔 문제분석

• 문자열을 정렬하게되면 문자열이 a,b,c,d…z 순서대로 오름차순으로 정렬이 된다.
• 정렬된 문자열을 기준으로 for?? 를 찾고싶다면 foraa와 forzz을 이분탐색으로 leftindex와 rightindex를 구하여 뺀 값이 for??와 일치하는 문자열임을 알 수 있다.
• 접미사에 ??가 붙은경우는 위의 문제로 풀고, 접두사에 ??가 붙은경우에는 문자열을 뒤집은뒤 풀면 된다.

📝 의사코드

• 입력받은 문자를 길이 기준으로 문자열을 저장한다.
• 거꾸로되지않는 문자열과, 거꾸로 저장된 문자열배열을 저장한다.
• 파이썬의 bisect_left와 bisect_right 함수를 이용하여 정렬된 문자열에서 원하는 문자열의 개수를 찾는다.
• query는 접두사가 ? 인경우는 뒤집고, 뒤집은 배열에서 이분탐색을 한다.
• 그외의 접미사가 ? 이거나 없거나 일경우는 일반 배열에서 이분탐색을 한다.
• 이분탐색한 결과를 배열에 저장하여 출력한다.

💻 코드

from bisect import bisect_left
from bisect import bisect_right

def solve(array, start, end):
    left = bisect_left(array, start)
    right = bisect_right(array, end)
    return right - left
    

def solution(words, queries):
    new_words = [[] for _ in range(100001)]
    reversed_new_words = [[] for _ in range(100001)]
    for word in words:
        new_words[len(word)].append(word)
        reversed_new_words[len(word)].append(word[::-1])
        
    # 단어순으로 정렬한다.
    for word in new_words:
        word.sort()
        
    for word in reversed_new_words:
        word.sort()
    
    answer = []
    for query in queries:
        if query[0] == '?':
            # 접미사가 ? 라면 거꾸로 뒤집어서 탐색한다.
            answer.append(solve(reversed_new_words[len(query)], query[::-1].replace('?', 'a'), query[::-1].replace('?', 'z')))
        else:
            # 접두사가 ? 라면 그냥 탐색해본다.
            answer.append(solve(new_words[len(query)], query.replace('?', 'a'), query.replace('?', 'z')))
            
    return answer

words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries = ["fro??", "????o", "fr???", "fro???", "pro?"]

print(solution(words, queries))

🎯 피드백 및 개선사항

• 트라이라는 자료구조로 문제를 해결 할 수 있습니다.
• words를 모두 Trie 자료구조에 넣은다음 queries를 통하여 문자열을 검색할때, 결과를 리턴한다.
• 주요점은 트라이의 노드마다 길이를 가지고 있어야 한다.

❓다른사람은 어떻게 풀었을까?

• 트라이 자료구조를 활용하여 문제를 해결한다.
• t1은 일반문자, t2는 뒤집어진 문자를 저장하는 트라이 자료구조이다.
• 트라이자료구조는 child, length 를 가지고 있다.
• child는 현재 문자열 word[0] 첫번째 문자열을 가르키고, 그 하위 node child은 word[1]을 가르키는 딕셔너리이다.
• length는 자기자신이 몇개의 단어를 가지고 있는지 저장하는 딕셔너리이다.

class Trie():
    def __init__(self):
        self.child = {}
        self.length = {}
        
    def push(self, word):
        node = self
        while len(word) > 0:
            node.length[len(word)] = node.length.get((len(word)), 0) + 1
            if word[0] not in node.child:
                node.child[word[0]] = Trie()
            node = node.child.get(word[0])
            word = word[1:]
            
    def search(self, word):
        node = self
        while len(word) > 0:
            if word[0] == '?':
                return node.length.get(len(word), 0)
            
            if word[0] not in node.child:
                return 0
            
            node = node.child[word[0]]
            word = word[1:]

def solution(words, queries):
    t1 = Trie()
    t2 = Trie()
    for word in words:
        t1.push(word)
        t2.push(word[::-1])
    
    answer = []
    for query in queries:
        if query[0] == '?':
            answer.append(t2.search(query[::-1]))
        else:
            answer.append(t1.search(query))
            
    return answer

words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries = ["fro??", "????o", "fr???", "fro???", "pro?"]

print(solution(words, queries))