[leetcode] 167. Two Sum II - Input Array Is Sorted 파이썬 코드

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

 

문제

 

오름차순으로 정렬된 배열이 있을 때 두 개의 숫자를 합했을 때의 값이 target이 되는 그 두 숫자의 index를 반환하는 문제이다.

 

Sol 1) 이진탐색

 

나는 이진탐색을 이용해 이 문제를 풀었다.

 

numbers라는 배열에서 숫자 하나씩 iterate 하면서 다른 짝꿍을 찾는 것이다.

예를 들어, numbers = [2, 7, 11, 15] 라는 배열과 target = 9가 있을 때

우선 2를 본다. 그러면 새로운 target은 9 - 2인 7이 된다. 7을 찾으면 두 숫자의 합이 target이 된다.

그리고 이 7을 찾을 때 이진탐색을 이용한다. 

 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        res = [0 for _ in range(2)]
        flag = False
        for i in range(len(numbers)):
            if flag:
                break
            ntarget = target - numbers[i] # new target
            lp, rp = i+1, len(numbers)-1
            res[0] = i+1
            while lp <= rp:
                mid = (lp + rp) // 2
                if numbers[mid] == ntarget:
                    res[1] = mid+1
                    flag = True
                    break
                elif numbers[mid] > ntarget:
                    rp = mid-1
                else:
                    lp = mid+1
            
        return res

 

 

풀긴 풀었는데 별로 효율적이지 못하다.

---

Sol 2) Two pointer 

numbers = [1, 3, 4, 5, 7, 10, 11]과 target = 9가 있을 때 

left pointer를 맨 처음에 두고, right pointer를 맨 뒤에 둔다.

1+11 > 9 이므로 right pointer를 왼쪽으로 옮긴다.

1+10 > 9 이므로 right pointer를 왼쪽으로 옮긴다.

1+7 < 9 이므로 left pointer를 오른쪽으로 옮긴다.

이런 식으로 하다보면, 문제에서 무조건 정답이 하나 있다고 했기 때문에 정답을 찾을 수 있다.

 

two pointer를 사용하면 linear 하게 풀 수 있다. O(n)

 

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

 

 

참고

https://youtu.be/cQ1Oz4ckceM?si=uh7koTRH_oENQwl6