[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 가사 검색

Posted on by

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘가사 검색’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60060에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다. 본 문제의 정답 코드는 효율성 테스트 2번을 통과하지 못하였습니다.

공식 풀이는 링크를 참조하시기 바랍니다.

가사 검색

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60060
카테고리 : Trie, BinarySearch
난이도 : 보통

문제 요약

단어들의 리스트가 주어진다. 이후에 검색 쿼리가 주어지는데, 이 검색 쿼리에 해당하는 단어의 숫자를 리턴하면 된다.

검색 쿼리는 쿼리의 앞이나 뒤에 ‘?’를 포함할 수 있다. 단 여기서 주어지는 쿼리는 ‘?’가 항상 쿼리의 맨 앞이나 뒤에서 연속되게 존재한다. 예를 들어 “??abc”나 “abc??”는 가능하지만 “a?b?c”나 “?abc?”와 같은 형태는 불가능하다.

문제 풀이

두 개의 딕셔너리를 사용해 이분 검색을 수행하는 방식을 사용할 것이다.

딕셔너리 초기화

우선 두 개의 딕셔너리를 초기화한다. 딕셔너리는 같은 길이를 가지는 단어들의 리스트를 저장한다. 이 때 다른 하나의 딕셔너리는 단어를 저장할 때 단어의 글자 순서를 역순으로 저장한다.

딕셔너리의 각 키에 해당하는 리스트에 대해 리스트 내의 단어들을 정렬시킨다. 이로서 딕셔너리는 단어를 길이별로 저장하고 저장된 단어는 리스트 내에서 알파벳순으로 정렬된 상태로 존재한다.

‘?’가 끝에 존재하는 쿼리

이제 각각의 쿼리를 처리한다. 쿼리의 문자를 왼쪽에서부터 오른쪽으로 처리할 것이다. ‘abc??’와 같이 ‘?’가 쿼리의 끝에 존재한다고 가정하자. 딕셔너리에서 키가 5인 리스트를 받아온다. 그리고 현재 쿼리에 해당하는 인덱스의 시작과 끝을 head와 tail에 저장한다.

가장 초기 상태에서 head = 0이고 tail은 리스트 길이 – 1의 값을 갖는다. 단어의 왼쪽부터 오른쪽까지 글자를 하나씩 처리한다. 현재 구간에 속한 단어들 중 처리해야하는 글자와 같은 글자를 갖는 구간을 새롭게 구한다.

가령 리스트가 [‘aaa’, ‘bba’, ‘bbb’, ‘bbc’, ‘ccc’] 이고 쿼리가 ‘bb?’라고 주어진다면 가장 첫 번째 문자 ‘b’에 대해 [0, 4]이던 구간은 [1, 3]으로 변하게 된다. 이 구간을 찾는 방법은 이분검색을 통해 찾아낼 수 있다. 이런 식으로 구간을 줄여나가다가 ‘?’를 만나게 되면 이후의 문자들은 모두 ‘?’일 것이므로 더 이상의 필터링 조건이 없는 것과 같다. 따라서 이 구간에 속하는 단어들의 갯수는 tail – head + 1이다.

‘?’가 앞에 존재하는 쿼리

만약 쿼리가 ‘?’로 시작할 때 이 쿼리를 뒤집으면 ‘?’가 끝에 존재하는 쿼리로 바뀌게 된다. 단 탐색 순서가 바뀌었기 때문에 사용되는 딕셔너리 또한 뒤집힌 단어들로 만들어져야만 한다. 이것이 두 개의 딕셔너리가 필요한 이유이다.

정답 코드

import copy
 
def search(c, idx, words, head, tail):
    if words[head][idx] == c and words[tail][idx] == c:
        return head, tail
 
    if head >= tail:
        return –1, –1
    
    MID = (head + tail) // 2
    left = search(c, idx, words, head, MID)
    right = search(c, idx,  words, MID + 1, tail)
    
    if left[0] != –1 and right[0] != –1:
        return left[0], right[1]
    if left[0] != –1:
        return left[0], left[1]
    if right[0] != –1:
        return right[0], right[1]
    return –1, –1
 
def solution(words, queries):
    result = [0] * len(queries)
    used_dic = {}
    dic = {}
    reverse_dic = {}
 
    words = list(set(words))
    for i in range(len(words)):
        word = words[i]
        length = len(word)
        if length not in dic:
            dic[length] = []
            reverse_dic[length] = []
        dic[length].append(word)
        reverse_dic[length].append(word[::–1])
        
    for key in dic:
        dic[key].sort()
        reverse_dic[key].sort()
        
    used_query = {}
    for i in range(len(queries)):
        orig_query, query = queries[i], queries[i]
        
        if query in used_query:
            result[i] = used_query[query]
            continue
        length = len(query)
        if length not in dic:
            result[i] = 0
            continue
            
        idx = 0
        picked_dic = dic
        if query[0] == ‘?’:
            query = query[::–1]
            picked_dic = reverse_dic
            
        head, tail = 0, len(dic[length]) – 1
        for k in range(length):
            if query[idx] != ‘?’:
                head, tail = search(query[idx], idx, picked_dic[length], head, tail)
                idx += 1
            else:
                break
        if head != –1:
            answer = max(tail – head + 1, 0)
        else:
            answer = 0
        used_query[orig_query] = answer
        result[i] = answer
    return result
cs

Competition 카카오 블라인드 채용 가사 검색