[LeetCode] #167. Two Sum 2 (Python)

작성일시: 2023년 7월 21일 오전 10:50
Level : Medium

알고리즘 스터디 시간에 JB 선배가 준비한 리트코드 문제! 난이도는 “Medium”이다.

📖Problems: #167. Two sum 2

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
찾은 두 숫자의 index를 각각 *index1 *and index2라고 할 때, 이에 각각 1을 더한 길이 2의 정수 배열을 반환하라.

The tests are generated such that there is exactly one solution. You may not use the same element twice.
정확히 하나의 솔루션만 있도록 테스트가 생성되었으니 걱정마라. 동일한 요소를 두번 사용할 수는 없다.

Your solution must use only constant extra space.
솔루션은 일정한 Extra space만 사용해야한다.

 

요약:
오름차순으로 정렬된 숫자의 배열에서, 더했을 때 주어진 특정 Target 숫자가 되는 두 숫자를 찾아라!

예시를 보면 더 이해하기 쉬울 것이다.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

🔍Institution

문제 유형 : two pointers

문제를 보자마자 브루트포스와 투포인터가 생각이 났다. 하지만 브루트포스는 대개 시간 복잡도가 좋지 않기 때문에 투포인터로 아이디어를 생각해보았다.

• 투포인터로 하려면 먼저 left, right를 나타낼 변수가 필요하다. left는 리스트의 가장 앞, right는 리스트에서 가장 마지막 인덱스를 나타낸다.
• 이후, 두 수를 더한 값이 target값과 같은 경우, target값보다 작은 경우, target값보다 큰 경우 이렇게 3가지의 경우의 수가 나뉜다. 따라서 이 부분은 if문으로 조건을 나눈다.
• 해당 조건들에서 어떤 경우에 left를 움직일지, right를 움직일지, 바로 return할지를 생각해보아야 한다.

아래에서 더 자세히 살펴보자.

 

🔍Approach

문제 풀 때는 안 봤지만, 정리할 때 도움이 되는 것 같아서 JB선배의 피피티 내용을 가져왔다.

kotress (http://kortress.com/)

위에 말한 것처럼 어떤 경우에 left를 움직일지, right를 움직일지, 바로 return할지를 생각해보아야 한다. 우린 이미 주어진 이 리스트가 “오름차순 정렬”되어 있다는 것을 인지해야 한다. 두 수를 더한 값이 target값보다 작거나 클 때 항상 같은 solution을 낼 수 있기 때문이다.

• numbers[left]+numbers[right]의 값이 target값과 같다면,
  • 바로 left와 right값을 return한다.(이때, 문제에서 주어진 output을 보면 0번째 index를 1로 설정하고 있으므로 left+1, right+1을 return해야 한다)
• numbers[left]+numbers[right]의 값이 target값보다 작다면,
  • 위의 예처럼 target이 18이지만 두 수를 더한 값이 17이라면, left나 right가 더 큰 수로 옮겨져야 한다. 이때 right는 이미 가장 큰 수를 가리키고 있으므로 left의 위치를 +1 해줘야 한다.
• numbers[left]+numbers[right]의 값이 target값보다 크다면,
  • 위의 예처럼 target = 18이고, 두 수를 더한 값이 22라면, left나 right중에서 더 작은 수로 옮겨가야 한다. 이때 left는 이미 작은 값이므로 right의 위치값을 -1해줘야 한다.

아래는 플로우차트이다.

Flow

numbers리스트, target값, left, right를 선언, return할 때는 +1이 되어야 함
left = 0, right = len(numbers)-1

1. numbers 리스트와 target값 입력 받음
2. if 조건 3개
   • numbers[left] + numbers[right] == target: 바로 결과단계로 넘어감 break
   • numbers[left] + numbers[right] > target: right -= 1
   • numbers[left] + numbers[right] < target: left += 1
3. 반복해야 한다. while의 조건 : left < right일 때
4. return(left+1, right+1)

 

🚩My submission

class Solution(object):
    def twoSum(self, numbers, target):
        left = 0
        right = len(numbers) - 1

        while left < right:
            if numbers[left] + numbers[right] == target:
                return(left+1, right+1)
            elif numbers[left] + numbers[right] > target:
                right -= 1
            elif numbers[left] + numbers[right] < target:
                left += 1


        for i in range(len(numbers)-1):
            for j in range(i+1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return(i+1, j+1)

시간복잡도 : O(n)

• 반복을 1번 하기 때문에 O(n)

공간복잡도 : O(1)

• numbers는 문제에 포함되어 있기 때문에, O(1)
• numbers 리스트까지 모두 포함한다면, numbers의 길이가 n이기 때문에 O(n)

너무 빨리 풀어버려서, JB선배가 브루트포스로도 해보라고 하셨다.

브루트포스로 하면 애초에 시간초과가 된다!! 근데 테스트케이스는 통과했다.

class Solution(object):
    def twoSum(self, numbers, target):       
        for i in range(len(numbers)-1):
            for j in range(i+1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return(i+1, j+1)

 

🚩Others submission

가장 위에 별을 많이 받은 python solution은 아래와 같다.

# two-pointer
def twoSum1(self, numbers, target):
    l, r = 0, len(numbers)-1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l+1, r+1]
        elif s < target:
            l += 1
        else:
            r -= 1

# dictionary           
def twoSum2(self, numbers, target):
    dic = {}
    for i, num in enumerate(numbers):
        if target-num in dic:
            return [dic[target-num]+1, i+1]
        dic[num] = i

# binary search        
def twoSum(self, numbers, target):
    for i in xrange(len(numbers)):
        l, r = i+1, len(numbers)-1
        tmp = target - numbers[i]
        while l <= r:
            mid = l + (r-l)//2
            if numbers[mid] == tmp:
                return [i+1, mid+1]
            elif numbers[mid] < tmp:
                l = mid+1
            else:
                r = mid-1

이 분은 투포인터 말고도, 딕셔너리, 이진탐색을 이용하여 푸셨다. 
새로운 유형을 생각해볼 수 있는 아이디어를 얻은 것 같다.
문제를 준비한 JB선배의 코드! 훨씬 깔끔해서 가져와보았다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            result = numbers[left] + numbers[right]
            if result > target:
                right -= 1
            elif result < target:
                left += 1
            else:
                return [left+1, right+1]

 

💡TIL

• 이런 문제 유형은 오히려 브루트포스를 생각하는게 더 어려운 것 같다.
• 생각보다 쉬운 문제였지만, 투포인터 개념을 오랜만에 다시 살펴보아서 좋았다. 근데 왜 쉬웠는지 생각해보니까 지난 학기 자료구조 시간에 배운, 이진탐색 내용이 도움이 되었던 것 같다.