[leetcode 2024/02/24] 167. Two Sum 2 - Input Array Is Sorted

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

Two Sum II - Input Array Is Sorted - LeetCode

 

1. 접근 방법

처음에는 binary search 같은 같지 않은 식으로 코드를 작성하였다.

선택한 두 값을 더한 것이 같다면 바로 해당 index 값들을 반환 해주었지만, 만약  그 값이 구하고자 하는 값보다 작다면,

min = min + 1, 

크다면, max = max - 1 을 해주었다.

 

다른 방식으로 푼 것은, 2중 for문으로 풀었다.

여기서 특징적으로 알 수 있는 것은 같은 수가 2개 이상 반복된다면, 같은 수끼리 더 이상 비교할 필요가 없다는 것이다.

[-1, -1, -1, -1, -1, .... 1, 1] 이고 2를 구해야할 때, 불필요한 계산들이 추가될 수 있다.

 

따라서 dictionary를 선언하여 받아오는 수에 대해서 dict[-1] += 1을 해주었다. 만약 그 수가 2를 넘어가면, 

즉 dict[-1] > 2 이다면, 더 이상 같은 -1을 비교할 필요가 없기 때문에 다른 수가 나올 때까지 2중 for문으로 넘어가지 않고 값들을 계산해 주었다.

 

2. 코드

--- binary search 이용 ---

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

        min = 0
        max = len(numbers) - 1

        while min <= max:

            mid = min + max // 2

            if numbers[min] + numbers[max] == target:
                return [min + 1, max + 1]
            elif numbers[min] + numbers[max] < target:
                min = min + 1
            else:
                max = max - 1

 

--- 2중 for문을 이용 ---

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        multiple_num = defaultdict(int)
        for i in range(len(numbers)):
            new = numbers[i]
            multiple_num[new] += 1
            if multiple_num[new] > 2:
                while numbers[i] == new:
                    i += 1 

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