[이진탐색] 가사 검색 (bisect 라이브러리 사용)

✅ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

✅ 접근 방법

🔴 첫번째 시도(틀림)

찾고자 하는 단어를 '?'를 중심으로 자르고 keyword에 저장한다음 이진 탐색으로 탐색하는 방법으로 시도했다. 해당 키워드를 words 배열에서 찾았을 때 `start += 1` 해서 다시 words에 키워드가 있는지 검사하는 방법으로 했는데 이렇게 하면 동일한 가사가 검색 될 경우도 있어서 당연히 틀렸다. 

아래 코드와 같이 작성함

def binary_search(start, end, target, count, words):
  word = target[0]
  start_idx = target[1]
  length = target[2]
  while True:
    if start > end:
      return count
      # print(count)


    mid = (start + end) // 2


    if word == str(words[mid][start_idx:start_idx+len(word)]):
        if length == len(words[mid]):
            print(start, end, mid)

            count += 1
            start += 1

            # print(words[mid][start_idx:start_idx+len(word)])
        elif length < len(words[mid]):
            end = mid - 1
        elif length > len(words[mid]):
            start = mid + 1

    elif word < str(words[mid][start_idx:start_idx+len(word)]): #두 
        # print(end)
        end = mid - 1


    elif word > str(words[mid][start_idx:start_idx+len(word)]):
        # print(start)
        start = mid + 1



def solution(words, queries):
  answer = []
  keyword = []
  words.sort()
  print(words)
  for i in queries:
      to_find = i.split("?")
      for k in range(len(to_find)):
          if to_find[k] != '':
              keyword.append((to_find[k], k, len(i)))

  for i in keyword:
      cnt = 0
      cnt = binary_search(0, len(words)-1, i, cnt, words)
      answer.append(cnt)

  return answer

 

🔴 두번째 시도(틀림)

여기서부터 chat gpt와 이코테 책의 도움을 빌려서 풀이하기 시작했다....

1. 접미사가 들어간 단어를 탐색하기 위한 reverse 배열을 만들어야 한다.
   • 찾고자 하는 단어가 접두사 또는 접미사이기 때문에 접미사가 들어간 가사를 찾기 위해 words 요소를 뒤집어서 정렬한 새로운 배열(words_reverese)가 필요하다는 것까지 아이디어를 떠올렸다.
2. 단어 길이에 따른 요소 배치 (이 생각을 못해서 많이 애먹었다...)
   • 여기서 words 배열에 있는 요소를 단어 길이에 따라 따로 저장해주면 쉽게 구현할 수 있었다. -> 이 생각을 못해서 계속 words 배열에서만 탐색 하다보니 
3. 키워드가 들어간 단어를 직접 탐색해서 수를 세는 것이 아니라 정렬된 배열에서 키워드가 들어간 단어의 첫번째 인덱스 위치와 마지막 인덱스 위치를 찾는 것이다.
   • 중복된 가사를 검색하지 않기 위해서 '?'위치에 'a'와 'z'을 넣어서 a를 넣은 키워드가 위치할 인덱스와 z를  넣은 키워드가 위치할 인덱스를 찾아서 이 두개를 빼면 키워드가 포함된 가사의 개수를 찾을 수 있다.

아래 코드와 같이 작성 했다.

def binary_search(start, end, target, words):
    #target이 정렬된 words 어디에 위치해야하는지 탐색
    if len(words) == 1:
        if words[0] < target:
            start = 1
        elif words[0] > target:
            start = 0
        return start
    while start < end:
        mid = (start + end) // 2

        if words[mid] < target:
            start = mid + 1
        elif words[mid] > target:
            end = mid #mid-1을 하지 않는 이유는 target이 words[mid]보다 작을경우 target은 words의 mid에 위치해야한다. 그래야 words[mid]의 값이 target뒤에 위치하게 된다.
    return start #start가 end보다 커지면 탐색을 모두 마친것이고 start의 위치가 target이 words에 위치할 인덱스가 된다.

def solution(words, queries):
	answer = []
    words.sort()
    words_reversed = []
    for word in words:
        words_reversed.append(word[::-1])
    words_reversed.sort()

    #길이에 따라 리스트를 따로 두어서 비교해야함!!!
    words_length = [[] for i in range(100000)]
    for word in words:
        words_length[len(word)].append(word)
    #접미사 탐색을 위한 word reverse 리스트 만들기

    words_reverse = [[] for i in range(100000)]
    for word in words_reversed:
        words_reverse[len(word)].append(word)

    #queries에서 ?를 a와 z로 바꾸고 각각 탐색
    for target in queries:
        #이렇게하는건 전치사일 경우 상관없는데 접두사일 경우는...? 접두사는 문자열 뒤집어서 탐색
        if target[0] == '?': #접미사이면
            left_target = target.replace('?', 'a') #left = left_target이 words에서 위치한 인덱스 +1
            right_target = target.replace('?', 'z') #right = right_tartget이 words에서 위치한 인덱스
            left_idx = binary_search(0, len(words_reverse[len(target)])-1, left_target[::-1], words_reverse[len(target)])
            right_idx = binary_search(0, len(words_reverse[len(target)])-1, right_target[::-1], words_reverse[len(target)]) + 1
        else:
            left_target = target.replace('?', 'a') #left = left_target이 words에서 위치한 인덱스 +1
            right_target = target.replace('?', 'z') #right = right_tartget이 words에서 위치한 인덱스

        #right - left하면 words안에 target수를 구할 수 있다.
        # left, right 각각 이진탐색 시작
            left_idx = binary_search(0, len(words_length[len(target)])-1, left_target, words_length[len(target)])
            right_idx = binary_search(0, len(words_length[len(target)])-1, right_target, words_length[len(target)]) + 1
            answer.append(right_idx - left_idx - 1)


    return answer

 

근데 입출력 예시만 맞게 나오고 코드 제출하니까 테케가 모두 실패로 뜸....

 

chat gpt의 도움을 받아 코드 최적화해서 제출하니 정답.... 

최적화된 코드는 아래와 같다

🟢 정답 코드

def binary_search(start, end, target, words):
    #target이 정렬된 words 어디에 위치해야하는지 탐색

    while start < end:
        mid = (start + end) // 2

        if words[mid] < target:
            start = mid + 1
        elif words[mid] > target:
            end = mid #mid-1을 하지 않는 이유는 target이 words[mid]보다 작을경우 target은 words의 mid에 위치해야한다. 그래야 words[mid]의 값이 target뒤에 위치하게 된다.
    return start #start가 end보다 커지면 탐색을 모두 마친것이고 start의 위치가 target이 words에 위치할 인덱스가 된다.
    
            

    
def solution(words, queries):
    answer = []
    words.sort()
    words_reversed = []
    for word in words:
        words_reversed.append(word[::-1])
    words_reversed.sort()

    #길이에 따라 리스트를 따로 두어서 비교해야함!!!
    words_length = [[] for i in range(10001)]
    for word in words:
        words_length[len(word)].append(word)
    #접미사 탐색을 위한 word reverse 리스트 만들기
    
    words_reverse = [[] for i in range(10001)]
    for word in words_reversed:
        words_reverse[len(word)].append(word)
    
    #queries에서 ?를 a와 z로 바꾸고 각각 탐색
    for target in queries:
        #이렇게하는건 전치사일 경우 상관없는데 접두사일 경우는...? 접두사는 문자열 뒤집어서 탐색
        if target[0] == '?': #접미사이면
            left_target = target.replace('?', 'a')[::-1] #left = left_target이 words에서 위치한 인덱스 +1
            right_target = target.replace('?', 'z')[::-1] #right = right_tartget이 words에서 위치한 인덱스
            word_search = words_reverse[len(target)]
            # left_idx = binary_search(0, len(words_reverse[len(target)])-1, left_target[::-1], words_reverse[len(target)])
            # right_idx = binary_search(0, len(words_reverse[len(target)])-1, right_target[::-1], words_reverse[len(target)]) + 1
        else:
            left_target = target.replace('?', 'a') #left = left_target이 words에서 위치한 인덱스 +1
            right_target = target.replace('?', 'z') #right = right_tartget이 words에서 위치한 인덱스
            word_search = words_length[len(target)]
        #right - left하면 words안에 target수를 구할 수 있다.
        # left, right 각각 이진탐색 시작
        left_idx = binary_search(0, len(word_search[len(target)])-1, left_target, word_search)
        right_idx = binary_search(0, len(word_search[len(target)])-1, right_target, word_search)

        answer.append(right_idx - left_idx)
        
                
    return answer

 

 

✅ 새롭게 알게 된 것 (bisect 라이브러리)

위에서 '?'에 'a'를 넣은 단어의 위치를 찾을때 라이브러리를 사용하지 않고 찾았는데, 이것을 위한 라이브러리가 있더라

 

바로 `bisect`

 

이 라이브러리는 이진탐색을 쉽게 구현할 수 있도록 제공해준다.

`bisect_left()` 와 `bisect_right()` 함수가 가장 중요하게 사용되고, 두 함수의 시간 복잡도는 `O(logN)` 에 동작한다고 한다.

• `bisect_left(a, x)`: 정렬된 순서를 유지하면서 리스트 a에서 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• `bisect_right(a, x)`: 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

 

위 두 한수는 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수를 구하고자 할 때 효과적으로 사용될 수 있다. (해당 문제와 같은 상황...)

 

파이썬의 라이브러리를 적극 사용하자..