68. Two Sum II - Input array is sorted

🎯 leetcode - 167. Two Sum II - Input array is sorted

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 68번 문제

📌 날짜

2020.03.01

📌 시도 횟수

3 try

💡 Code

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

💡 문제 해결 방법

0. 이미 정렬된 배열이므로 투 포인터를 사용할 수 있다. 
1. left는 0에서, right는 len(numbers)-1 에서 시작한다.
2. cal_sum은 left, right가 위치하고 있는 값의 합이다.
3-1. cal_sum이 target보다 크면...
값을 줄여줘야 되니까 right -= 1
3-2. cal_sum이 target보다 작으면...
값을 키워야 되니까 left += 1
3-3. cal_sum == target이면...
return (left + 1, right + 1)	# 문제에서 1에서부터 시작하는 인덱스라고 했다~

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 이진 검색으로 나머지 값 판별

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

💡 문제 해결 방법

- 첫번째 숫자는 for문으로 앞에서부터 차례대로 접근하고,
첫번째 숫자에 두번째 숫자를 더했을 때 target이 되어야 하므로 두번째 숫자는
>> expected = target - (cur_num) 이되어야 한다.
- 그리고 두번째 숫자(expected)가 나머지 범위 안에 있는지를 이진 검색으로 판별한다.

---

📌 둘. 슬라이싱 없이 bisect

슬라이싱은 빠르고 편리한 모듈이지만 무분별한 슬라이싱의 사용은 오히려 속도 저하의 주범이 될 수 있닫. 꼭 필요한 곳에만 적절히 사용하자!

import bisect

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, cur_num in enumerate(numbers):
            expected = target - cur_num
            i = bisect.bisect_left(numbers, expected, idx + 1) 	# 현재 cur_num의 [idx+1~끝] 범위에 target이 있는지 검사
            if i < len(numbers) and numbers[i] == expected:	# 만약 target이 존재하면
                return idx + 1, i + 1

💡 문제 해결 방법

- 첫번째 숫자는 for문으로 앞에서부터 차례대로 접근하고,
첫번째 숫자에 두번째 숫자를 더했을 때 target이 되어야 하므로 두번째 숫자는
>> expected = target - (cur_num) 이되어야 한다.
- 그리고 두번째 숫자(expected)가 나머지 범위 안에 있는지를 이진 검색으로 판별한다.

💡 새롭게 알게 된 점

- bisect_left(a, x, lo = 0, hi = len(a))
1. lo는 왼쪽 범위를 제한한다.
2. hi는 오른쪽 범위를 제한한다.