Problem Solving/프로그래머스

[Level 4 프로그래머스] 카카오 기출, 2020 KAKAO BLIND RECRUITMENT - 가사 검색(Python)

돌돌김 2021. 1. 6. 02:30

programmers.co.kr/learn/courses/30/lessons/60060

 

코딩테스트 연습 - 가사 검색

 

programmers.co.kr

트라이(Trie) 자료형을 사용하여 풀 수도 있지만, 이분탐색을 사용해서 풀어보았다.

이분탐색은 따로 구현하지 않고 Python의 bisect 라이브러리를 활용하였다.

 

 

 

문제 해결
  1. 2개의 배열을 사용한다. 각각 주어진 단어, 단어의 순서를 반대로 한 단어를 리스트에 추가한다.
    • 예를들면 "frodo"라는 단어를 "frodo"와 "odorf"로 나누어 각각의 배열에 담는다.
    • 단어의 순서를 바꾸는 것은 word[::-1] 을 하여 append 하면 거꾸로 담긴다
  2. 각 배열을 이분탐색을 하기 위해 정렬한다. 
  3. queries가 접미사인지, 접두사인지 구분하고 그에 맞게 이분탐색을 한다
    • 접미사인 경우(ex. fro??) 
    • 접두사인 경우(ex. ????o)
      • 이 2개의 경우를 구분해서 탐색해야 하므로 각각을 따로 담아야한다.
      • 단순한 dictionary 자료형이 아닌 defaultdict를 사용했다. defaultdict는 collections 모듈에 있는 메소드인데, dictionary와 달리 초깃값을 int, list, set 등으로 설정할 수 있다. defaultdict에 대한 설명은 여기를 참고하면 좋을 듯 하다.
  4. 이분탐색의 결과를 answer에 추가한다.

 

이 문제에서 중요한 것은 단어의 길이 이다. 

 

입출력 예제를 보면 

word queries result
["frodo", "front", "frost", "frozen", "frame", "kakao"] ["fro??", "????o", "fr???", "fro???", "pro?"] [3, 2, 4, 1, 0]

아래 두 키워드는 와일드카드가 접미사에 있고, "fro" 만 포함되어있다는 공통점이 있지만 단어의 길이에서 차이가 있다.

  • fro??
  • fro???

queries의 키워드를 사용해서 word를 찾을 때, 길이가 서로 다른 경우는 고려하면 안되기 때문에 이를 구분해야한다.

때문에 defaultdict를 사용하여 key값에 단어의 길이를 넣고, value에 단어 길이가 동일한 단어들만 넣고 정렬한 것이다.

 

 

소스코드
import bisect
from collections import defaultdict

def solution(words, queries):
    answer = []
    # value를 list로 할 것이므로 defaultdict를 사용해서 value를 list로 초기화한다
    forward = defaultdict(list)
    backward = defaultdict(list)
    
    # key:문자의 길이, value:문자 
    for word in words:
        forward[len(word)].append(word)
        backward[len(word)].append(word[::-1]) # 와일드카드가 접미사에 붙은 경우 
    
    # 문자를 사전순으로 정렬
    for f_word in forward.values():
        f_word.sort()
    for b_word in backward.values():
        b_word.sort()
        
    for query in queries:           
        if query[0] == '?': # 접두사 -> 역순으로 정렬된 리스트에서 이분탐색    
            query = query[::-1]
            le = bisect.bisect_left(backward[len(query)], query.replace('?', 'a'))
            ri = bisect.bisect_left(backward[len(query)], query.replace('?', 'z'))
        else: # 접미사
            le = bisect.bisect_left(forward[len(query)], query.replace('?', 'a'))
            ri = bisect.bisect_left(forward[len(query)], query.replace('?', 'z'))   
        answer.append(ri-le)        
    return answer

 

 

확실히 이분탐색이 속도가 빠르다.