[LeetCode] Two Sum II

1번. 이진 검색 - bisect 파라미터

from collections import defaultdict
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, num in enumerate(numbers):
            ex = target - num
            idx = bisect.bisect_left(numbers, ex, i+1)
            if idx < len(numbers) and numbers[idx] == ex:
                return [i+1, idx+1]

Runtime: 147 ms

• 슬라이싱하면 시간이 너무 오래 소요됐는데, bisect의 파라미터 중 왼쪽 범위를 제한하는 파라미터인 lo를 이용하면 속도가 아주 많이 빨라진다.
  bisect.bisect_left(list, target, lo=0, hi=len(list)

2번. 이진 검색 - 투 포인터

from collections import defaultdict
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, num in enumerate(numbers):
            ex = target - num
            left, right = i+1, len(numbers)-1
            while left <= right:
                mid = (left+right) // 2
                if ex > numbers[mid]:
                    left = mid + 1
                elif ex < numbers[mid]:
                    right = mid - 1
                else:
                    return i+1, mid+1           

Runtime: 198 ms

• bisect 모듈을 이용하지 않고 투 포인터로 이진 검색을 구현
• mid = (left + right) // 2
• 정렬된 리스트에서 합이 target인 짝을 찾는 것이기 때문에 현재 인덱스 뒤에부터 검색하면 됨.
  -> left = i+1
  => 이러면 자기 값을 중복으로 더한 값이 target인 경우를 정답처리하지 않는다. ex([3,3])
  정답 처리하는 문제가 나오면 그냥 left = i로 범위를 지정하면 된다.

3번. bisect + 슬라이싱

1) 슬라이싱 남용

from collections import defaultdict
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, num in enumerate(numbers):
            ex = target - num
            idx = bisect.bisect_left(numbers[i+1:], ex)
            if idx < len(numbers[i+1:]) and numbers[i+1:][idx] == ex:
                return [i+1, idx+i+2]

Runtime: 5500 ms
엄청난 런타임

2) 변수에 저장해서 한 번만 슬라이싱하게 슬라이싱 최소화

from collections import defaultdict
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, num in enumerate(numbers):
            ex = target-num
            nums = numbers[i+1:]
            idx = bisect.bisect_left(nums, ex)
            if idx < len(nums) and nums[idx] == ex:
                return [i+1, idx+i+2]

Runtime: 2428 ms
1) 보다 반으로 줄었지만 여전히 엄청난 런타임.

테스트 케이스의 입력값이 매우 커서 슬라이싱에서 속도 저하가 발생하는 것 같다.
슬라이싱이 아무리 빠르더라도 남용 금지~!