[Leetcode] 167. Two Sum II - Input Array Is Sorted_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '167. Two Sum II - Input Array Is Sorted'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Two Sum II - Input Array Is Sorted' 알고리즘 문제

 

STEP 2. 'Two Sum II - Input Array Is Sorted' 코드(code)

 

STEP 3. 'Two Sum II - Input Array Is Sorted' 해설

 

STEP 4. 'Two Sum II - Input Array Is Sorted' solution

 

반응형

 

STEP 1. 'Two Sum II - Input Array Is Sorted' 알고리즘 문제

 

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. 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.

 

오름차순으로 정렬되어 있는 1d 인덱스 정수 배열이 주어지면 특정 목표 숫자에 합산되는 두 개의 숫자를 찾습니다. 이 두 숫자를 numbers[index1]과 numbers [index2]로 둡니다. 여기서 1 <= index1 < index2 <= numbers.length 입니다.

정수 배열 [index1, index2]로 1을 더한 두 index1과 index2의 인덱스를 반환합니다. 테스트는 정확히 하나의 해가 있도록 생성됩니다. 동일한 요소를 두 번 사용할 수 없습니다. 솔루션은 일정한 추가 공간만 사용해야 합니다.

 

Constraints:

 

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

 

---

STEP 2. 'Two Sum II - Input Array Is Sorted' 코드(code)

 

■ Runtime: 104ms Beats 61.93%
■ Memory: 17.74MB Beats 48.50%

 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dict_ = dict()

        for idx in range(len(numbers)):
            target_check = target - numbers[idx]
            if target_check not in dict_:
                dict_[numbers[idx]] = idx
            else:
                return [dict_[target_check]+1, idx+1]

---

STEP 3. 'Two Sum II - Input Array Is Sorted' 해설

 

오름차순으로 정렬된 array를 이동하면서 hash table에서 target - numbers[idx] 값이 있는 경우, 정답을 반환하는 방식입니다. 이 보다 더 효율적으로 two pointer를 활용해서 left, right index를 이동하면서 계산할 수 있습니다. 해당 방법은 아래에서 자세하게 살펴보겠습니다.

 

 

STEP 4. 'Two Sum II - Input Array Is Sorted' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 109ms Beats 31.59%
■ Memory: 17.84MB Beats 48.50%

 

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

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

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '167. Two Sum II - Input Array Is Sorted'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.