[이진탐색 문제] Leetcode 1268. 1268. Search Suggestions System

문제

https://leetcode.com/problems/search-suggestions-system/

이 문제는 주어진 제품 목록에서 주어진 검색어에 대한 제안을 반환하는 것으로, 각 검색어 접두사에 대해 최대 세 개의 제안을 만들어야 합니다.

문제풀이

from bisect import bisect_left,bisect_right

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        ans=[]
        products.sort() 
        for i in range(1,len(searchWord)+1):
            index = bisect_left(products, searchWord[0:i])
            max_index=bisect_right(products,searchWord[0:i]+ chr(ord('z') + 1))
            ans.append(products[index:min(index+3,max_index)]) 
        return ans
        

주어진 products를 정렬 후 이진탐색을 각각 좌우로 수행하여 추천범위를 확정하여 ans배열에 누적하면서 값을 return한다.

Lookback

1. 해당 문제를 풀 떄 핵심은 bisect_right 처리시 z를 아스키코드로 변환 후 1을 더하는 부분이다. 해당 작업을 하지 않는다면 products의 마지막 인덱스 범위 내에 입력한 검색어와 동일한 숫자를 산출하고 3과 비교하여 작은 값까지를 max 범위로 가져가는 로직을 만들어야 하는데(쓰면서도 복잡하다..) 위와 같이 처리하면 이진탐색만으로 한줄로 최대 범위를 산출하는 효과를 만들 수 있었다. 속도 부분에서 우위를 점할 수 있었던 것도 이와 같은 로직 덕분으로 보인다.