[파이썬 알고리즘 인터뷰][이진검색] 두 수의 합2

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

합이 target이 되는 두 수의 인덱스 출력

 

책에서 구현된 코드

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            expected = target - v
            i = bisect.bisect_left(numbers, expected, k + 1)
            if i < len(numbers) and numbers[i] == expected:
                return k + 1, i + 1

 

기억해야할 기법

• bisect로 lo, hi를 설정할 수 있음

 

내가 구현한 코드

# 이진 검색
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        def bs(l, r, n):
            while l <= r:
                mid = l + (r - l) // 2
                if target < n + numbers[mid]:
                    r = mid - 1
                elif target > n + numbers[mid]:
                    l = mid + 1
                else:
                    return mid
            return l

        right = len(numbers)-1
        for i, n in enumerate(numbers):
            ans = bs(i+1, right, n)
            if ans < len(numbers):
                if numbers[ans] + n == target:
                    return [i+1, ans+1]
                right = ans

# 투포인터
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1
        while l < r and numbers[l] + numbers[r] != target:
            if numbers[l] + numbers[r] < target:
                l += 1
            elif numbers[l] + numbers[r] > target:
                r -= 1
        return [l+1, r+1]

• O(n log n)이 가장 좋은 방법이라 생각했는데 투포인터 O(n)이 있었다
• 혹시 O(log n)으로 가능할까 싶어서 고민해봤는데 안될 것 같다
  • 이진 탐색시 mid값을 중심으로 l과 r의 합을 target에 맞춰보려했음
  • 여러 조건들이 있음
    - mid + mid-1 < target이면 l = mid
    - target < mid이면 r = mid
  • 그러나 이런 조건들로 이분이 불가능