[leetcode] 167. Two Sum II - Input Array Is Sorted 풀이, 해설 (python)

문제 링크 

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

Two Sum II - Input Array Is Sorted - LeetCode

 

 

1차 풀이 

단순하게 모든 조합을 비교하면 O(n*n)이 걸리지만, 문제는 해결할 수 있을것 같았다. 

제약조건상 n이 30000 개이므로 최대 30000 * 30000 해서 그 방법으로는 접근하면 안될 것 같아서 다른 방법을 고민했다. 

 

그다음 생각했던 방식은, target과 현재 값을 비교해서, binary search를 활용해서 중간값부터 해서 계산하는 방법을 고민해봤는데, 

[-90, 1, 10, 100] 이 있을때 target=10이라고 했을때 답은 [100,-90]이기 때문에 binary search로 target과 근사값 10을 찾더라도 해결책이 아닐 수도 있을 거라는 생각을 했다. 

 

그래서 각 배열이 오름차순으로 정렬되어있는 것을 힌트로 알고리즘으로서 해결할 수 있는 방법을 고민하기 시작했다. 

주어진 예시, [2,7,11,15]에서 합 18을 구한다고 했을때, 

- 15 선택, 15 + 2 = 17 < 18 다음거 계산, 15 + 7 = 22 멈춤

- 11 선택, 11 + 7 = 18 종료 이런식으로 된다.

오름차순으로 정렬되어 있기 때문에 target과 비교해서 넘어갈 경우, 더이상 다음 값을 볼 필요가 없다. 

- 반대로 2선택, 2 + 7 = 9, 2 + 11 = 13, 2 + 15 = 17 target을 찾을때까지 계속 봐야하고 

- 7 선택, 7 + 11 = 18 종료  이런식으로 된다. 

 

 

이 개념을 가지고 알고리즘으로 짜면 다음과 같다. 

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        l, r = 0, len(numbers) - 1
        while l < r:
            if (numbers[l] + numbers[r]) == target : 
                break;
            elif (numbers[l] + numbers[r]) > target :
                r = r -1 
            elif (numbers[l] + numbers[r]) < target :
                l = l + 1 
        
        return [l + 1, r + 1]

 

 

해설 

https://www.youtube.com/watch?v=cQ1Oz4ckceM

위에 문제 풀었을때, 생각했던 개념을 해설에서 조금 더 쉽게 설명해서 가져오자면, 

[1,3,4,5,7,11]이 있고 target=9인 경우, 

먼저 1 + 11 = 13 < 9 인경우 포인터로 합을 줄일려면 오른쪽 포인터를 안쪽으로 한 칸 땡겨야 한다. 

그러면 1 + 7 = 8 > 9 로 오히려 값이 target보다 줄어들어서, 이제는 왼쪽 포인터를 오른쪽으로 한 칸 늘려야 한다. 

 

이런식으로 생각하는 방법도 있다고 한다.