(2020 KAKAO Blind Recruitment) 가사 검색

Problem

카카오 홈페이지 코멘트

  • 정답률
    • 정확성: 34.4%
    • 효율성: 0.8%
  • 출제 의도
    • 문자열을 다룰 수 있는지 파악
    • 트라이 자료구조 또는 이분 탐색등 보다 효율적인 방법을 이용해 코드를 작성할 수 있는지 파악
  • 해설
    • 정확성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하면서 개수를 세면 됩니다.
    • 효율성 풀이 queries에 담긴 문자열을 words에 담긴 문자열과 하나하나 비교하는 방법으로는 효율성 풀이를 통과할 수 없습니다.
    • queries에 담긴 문자열이 words에 있는지 탐색하는 효율적인 방법으로 트라이(Trie) 자료구조를 사용할 수 있습니다.
    • 이때, 원래 문자열을 이용해 만든 트라이와, 문자열을 뒤집어서 만든 트라이 두 개를 이용해야 합니다.
    • ???가 접두사인 경우는, 문자열을 뒤집어서 ???가 접미사로 나온다고 생각할 수 있기 때문입니다.
    • 예를 들어, “??ost”의 경우 “tso??”로 생각할 수 있습니다.
    • 단어를 트라이에 넣을 때는 길이에 따라 서로 다른 트라이에 넣어줘야 합니다. 
    • 같은 접두사를 가지더라도 길이에 따라 개수가 달라질 수 있기 때문입니다.
    • 단어 하나의 길이가 최대 1만이기 때문에 길이가 1인 문자열을 넣을 트라이부터 길이가 1만인 문자열을 넣을 트라이까지 생성합니다.
    • 이제 각 단어별로 길이에 맞는 트라이에 넣어줍니다.단어를 넣을 때는 각 문자별로 해당 노드의 count를 1씩 증가시켜 줍니다.
    • 이후에 단어를 검색할 때는 접두사에 해당하는 노드까지 이동한 후 해당 노드의 count를 return 하면 됩니다.
    • 이 외에도 문자열을 정렬한 다음 이분탐색하는 방법 등을 사용할 수 있습니다.

My solution

class Node(object): ## Trie Node 구성
    def __init__(self, key):
        self.key = key ## 시작값(이전의 값 개념)
        self.remain_length = {} ## Terminal까지 남아있는 문자열의 길이
        self.children = {} ## 자식
class Trie(object):
    def __init__(self):
        self.head = Node(None)

     def insert(self, string):
        ## key에는 문자, length에는 남아있는 string의 길이를 담았음
        curr_node = self.head

         remain_length = len(string)
        if remain_length in curr_node.remain_length:
            curr_node.remain_length[remain_length] += 1
        else:
            curr_node.remain_length[remain_length] = 1
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)

             curr_node = curr_node.children[char]
            remain_length -= 1
            if remain_length in curr_node.remain_length:
                curr_node.remain_length[remain_length] += 1
            else:
                curr_node.remain_length[remain_length] = 1

     def search_count(self, string, check_length):
        curr_node = self.head
        ## 찾아야할 "?" 포함한 string의 길이가 없다면 return 0
        if check_length+len(string) not in curr_node.remain_length:
            return 0
        
        for char in string:
            ## 찾아야할 string이 없다면 return 0
            if char in curr_node.children:                
                curr_node = curr_node.children[char]
            else:
                return 0
        ## string은 존재하는데 check_length가 remain_length에 있는지 확인!
        if check_length in curr_node.remain_length:
            return curr_node.remain_length[check_length]
        else:
            return 0
def solution(words, queries):
    t = Trie()
    inv_t = Trie()
    for word in words:
        t.insert(word)
        inv_t.insert(word[-1::-1])

     answer = []
    for i in range(len(queries)):
        query = queries[i]
        if query[0] is '?':  # 시작이 '?'
            query = query[-1::-1]
            chars = query.replace("?", "")
            check_length = len(query)-len(chars)
            # end = query.find('?')
            # chars = query[:end]
            answer.append(inv_t.search_count(chars, check_length))
        else: # 시작이 알파벳
            chars = query.replace("?", "")
            check_length = len(query) - len(chars)
            # end = query.find('?')
            # chars = query[:end]
            answer.append(t.search_count(chars, check_length))

     return answer

댓글

댓글 쓰기