[코딩테스트] 프로그래머스 - 가사 검색(2020 Kakao) in Python

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성.

 

?는 한 글자를 나타내는 와일드카드이다.

 

예시: words = ["frodo", "front", "frost", "frozen", "frame", "kakao"], queries = ["fro??", "????o", "fr???", "fro???", "pro?"]일때,

answer = [3, 2, 4, 1, 0]

 

잘못된 풀이

- 중첩의 중첩을 이용, 각 query마다 모든 단어의 모든 글자를 탐색하는 방법은, 역시나 효율성 테스트에서 실패했다.

- words (100,000 이하), 각 가사 단어 길이 (10,000 이하) 였을 때,

query 하나에 대해 탐색하는 것만으로도

최악의 경우 100,000 x 10,000 = 1,000,000,000이 되어 파이썬 효율성 리밋이라고 볼 수 있는 1억에 가까워지니 말이다.

 

효율성 실패의 현장 ↓

def solution(words, queries):
    answer = []
    
    for x in queries:
        count = 0
        for y in words:
            if len(x) == len(y):
                i = 0
                check = True
                for i in range(len(x)):
                    if x[i] != '?':
                        if x[i] != y[i]:
                            check = False
                            break
                if i == len(x) - 1 and check == True:
                    count += 1
        
        answer.append(count)
    return answer

 

 

제대로 된 풀이

- 탐색 시 시간이 훨씬 덜 드는 이진 탐색을 이용한다.

- 단어들을 글자 수별로 배열에 담아 나눈 후,

- 각 배열을 sort한다.

- "fro??"라는 query가 주어져있을 때, "froaa"와 "frozz" 사이의 단어 개수를 구하면 되는 것에 착안,

- bisect library (이진탐색)를 import하여, bisect_left(array, "froaa"), bisect_right(array, "frozz") 사이의 값을 구한다.

- 와일드카드가 접미사로 온 경우에는 (ex. "??odo"), 단어들을 거꾸로 만들어 같은 방법을 적용한다! (ex. "odo??")

 

- 이렇게 풀면 이진탐색은 log M의 복잡도를 띄기에, 시간 복잡도는 O(N log M)이 된다.

 

 

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    
    return right_index - left_index
    
def solution(words, queries):
    answer = []
    # 단어 길이 별 배열 초기화
    data = [[] for _ in range(10001)] # 각 가사 단어 길이는 1이상 10000이하
    reverse = [[] for _ in range(10001)]
    
    # 단어 넣어주기
    for word in words:
    	data[len(word)].append(word)
        reverse[len(word)].append(word[::-1])
        
    # 각 배열 정렬
    for i in range(10001):
    	data[i].sort()
        reverse[i].sort()
        
    # 본격적으로 찾기
    for q in queries:
    	if q[0] != '?':
        	res = count_by_range(data[len(q)], q.replace('?','a'), q.replace('?','z'))
        else:
        	res = count_by_range(reverse[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        answer.append(res)
        
    return answer