[이진 탐색] 가사 검색

1. 문제

가사 배열이 주어지고, query가 와일드카드 "?" 와 주어졌을 때, query와 일치하는 단어 수를 반환

 

2. 입력

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

 

3. 출력

# SET - 1
result = [3, 2, 4, 1, 0]

 

4. 풀이

여차하면 for문 여러번써서 풀수있지만, 그러면 효율성 테스트에서 시간초과가 난다.

최악의 경우 10000 * 10000 을 해야되기 때문

 

따라서 이는 bisect를 활용해 풀면되는데,

1. word를 앞으로, 뒤집어서 배열 2개를 만들고 정렬 (순서대로 나오게)

2. query에서 wildcard가 앞에 있는지 뒤에있는지 확인 (뒤에있으면 뒤집어서 확인)

3. wildcard를 a로 바꾼 경우와, z로 바꾼 배열에서 bisect검색 후 index차이를 반환 (검색된 개수)

 

for문으로 풀면 쉽지만 정답과는 거리가 멀어진다...

 

빠르게 푸는 방법을 찾는게 신기.. 오늘도 조금 더 배운다.

5. 코드

# NDB
from bisect import bisect_left, bisect_right

def count_by_range(a, lv, rv):
    ri = bisect_right(a, rv)
    li = bisect_left(a, lv)
    return ri - li

def solution(words, queries):
    answer = []
    word_list = [[] for _ in range(10001)]
    reversed_word = [[] for _ in range(10001)]
    for word in words:
        word_list[len(word)].append(word)
        reversed_word[len(word)].append(word[::-1]) # 뒤집기
    
    for i in range(10001):
        word_list[i].sort()
        reversed_word[i].sort()
        
    for q in queries:
        if q[-1] == '?':
            # 왼쪽 
            res = count_by_range(word_list[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
            # 앞부분이 같은 애들 중에서,
            ## 나머지를 aaa로 채웠을 떄 index는 가장 왼쪽
            ## 나머지를 zzz로 채웠을 때 가장 오른쪽
        else:
            # 오른쪽
            res = count_by_range(reversed_word[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z'))
        answer.append(res)
    return answer

# 내 풀이
def solution(words, queries):
    word_list = [[] for _ in range(10001)]
    for word in words:
        word_list[len(word)].append(word)
    answer = []
    for query in queries:
        temp = 0
        q_list = query.split('?')
        q_left = q_list[0]
        q_right = q_list[-1]
        query_len = len(query)
        if q_left:
            q_len = len(q_left)
            for word in word_list[query_len]:
                if q_left == word[:q_len]:
                    temp+=1
        else:
            q_len = len(q_right)
            for word in word_list[query_len]:
                if q_right == word[-q_len:]:
                    temp+=1

        answer.append(temp)
    return answer