이진 검색 예제, bisect_left 활용, 슬라이싱

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/submissions/

Two Sum II - Input Array Is Sorted - LeetCode

 

 1. 투 포인터

 이 문제는 배열이 정렬되어있기 때문에 투포인터를 사용할 수 있다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i,j=0,len(numbers)-1
        
        while i!=j:
            if numbers[i] + numbers[j]<target:
                i+=1
            elif numbers[i] + numbers[j] > target:
                j-=1
            else:
                return i+1,j+1

 투 포인터 풀이의 경우 O(n) 에 풀이할 수 있다.

 

 2. 이진 검색

 현재 값을 기준으로 나머지 값이 맞는지 확인하는 형태의 이진 검색 풀이를 시도해보자.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k,v in enumerate(numbers):
            left,right=k+1,len(numbers)-1
            expected=target-v
            
            while left<=right:
                mid= (left+right) //2
                
                if numbers[mid] < expected:
                    left=mid+1
                elif numbers[mid] > expected:
                    right=mid-1
                else:
                    return k+1, mid+1

 시간 복잡도는 O(nlogn)이 된다. 

 

 3. bisect모듈 + 슬라이싱

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

 코드가 엄청 깔끔해졌지만 앞선 이진 검색 풀이에 비해 20배 이상 느리다. 파이썬 슬라이싱을 무리하게 적용한 게 원인인것 같다.

 

 4. bisect 모듈 + 슬라이싱 최소화

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            sol=target-numbers[i]
            nums=numbers[i+1:]
            index=bisect.bisect_left(nums,sol)
            
            if index<len(nums) and numbers[i+index+1] == sol:
                return i+1, i+index+1+1

  이렇게 하니 앞선 풀이보다 2배가량 속도가 빨라졌다.

 

 5. bisect모듈 + 슬라이싱 제거

 앞선 포스팅을 보면 다음과 같이 기본 파라미터 외에도 여러 추가 파라미터가 있는 것을 발견했다.

 이 문서를 참고해서 왼쪽 범위를 제한하는 파라미터인 lo를 찾아냈고, 이 값을 지정하는 것으로 풀이를 진행했다. 이제 더 이상 슬라이싱을 사용할 필요가 없어졌다.

 

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

 이 경우 투포인터와 비슷한 성능을 낸다.