Two sum (twosum.py)

---

[문제]

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

[제한 사항]

• $2$ <= nums.length <= $10^4$
• $-10^9$ <= nums[i] <= $10^9$
• $-10^9$ <= target <= $10^9$
• Only one valid answer exists.

[입출력 예]

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

풀이

---

1차 시도

나의 로직

1. 브루트 포스 방식으로 풀어본다. 하지만 input의 갯수가 $n^2$ 시간복잡도로 풀기에는 $10^8$개라서 이 방법은 최선의 선택이 아닌것 같았다.
2. 슬라이딩 윈도우 방식으로 접근해 보았다.
   1. 더할 인덱스 위치를 어디서부터 설정해야 할 지 몰랐다.
   2. 어차피 랜덤한 숫자들의 배열이라 어디서 시작해도 상관 없을 것 같았다.
   3. 0번 인덱스와 마지막 인덱스를 더한 결과와 target을 비교한 뒤
   4. 같다면 그대로 인덱스들을 리턴, 다르다면 둘 중 하나의 위치를 옮겨야 한다.
   5. 옮기는 기준은 구한 결과가 target보다 작으면 방금 구한 결과보다 새로운 결과가 커지도록 옮긴다.
   6. 결과가 target보다 크다면 새 결과가 작아지는 방향으로 옮긴다.
   7. 그런데 이 기준으로 옮기면 결국 단뱡향으로 움직여야 한다. 안그러면 무한으로 왔다갔다 하는 상황이 발생하기 때문이다.
   8. 단방향으로 움직이다 보니 답을 못찾게 된다. 아까의 위치로 돌아가야 하는 상황도 있는데, 이에 대한 기준이 없다.
3. 단방향으로만 확실히 움직일 수 있도록 리스트를 정렬한 sortedNums라는 새로운 리스트를 만든다.
   1. 시작과 끝 위치에서 더한 결과와 target을 비교한다. 이 결과를 sum이라고 한다.
   2. target과 sum을 비교하여 같다면 인덱스들을 리턴한다.
   3. sum < target이면 시작 인덱스를 한 칸 뒤로 옮긴다.
   4. sum > target이면 끝 인덱스를 한 칸 앞으로 옮긴다.
   5. 그러나 이렇게 찾은 인덱스들은 원래 주어진 nums 배열의 인덱스와 다르다. 정렬된 새로운 리스트의 인덱스이기 때문이다.
   6. 그래서 target과 sum이 일치하는 두 값을 기준으로 원래 nums배열에서 해당 값들이 어떤 인덱스였는지 찾아서 리턴한다.
   7. nums.index()는 처음 나타난 인덱스만 리턴하므로, 뒤에서부터 찾는 메서드인 rindex(nums, value)를 따로 정의해 사용했다.

코드

class Solution:
    def rindex(self, list, val):
        return len(list) - 1 - list[::-1].index(val)

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted(nums);
        left = 0
        right = len(nums) - 1
        while left < right:
            sum = sortedNums[left] + sortedNums[right]
            if sum == target:
                return [nums.index(sortedNums[left]), self.rindex(nums, sortedNums[right])]
            if sum < target:
                left += 1
            elif sum > target:
                right -= 1

결과

배운점

• 시간복잡도를 활용하여 접근 방법이나 적용한 알고리즘에 대한 힌트를 얻는 방법을 배웠다.

• 배열이 주어지는 문제라면, 해당 배열의 정렬 여부가 어떤 알고리즘을 적용시킬지에 대한 힌트가 될 수 있다는 것을 배웠다.

• 정렬을 하는 것 자체도 실행시간에 포함되므로 정렬이 실행시간에 얼마나 영향을 미치는지 또한 염두에 두고 풀어야겠다.

(이번 문제에서는 정렬이 $O(nlogn)$, 반복문이 $O(n)$으로 정렬이 시간이 더 걸릴것으로 예상된다. 하지만 전체 시간복잡도가 nlogn이라 정답을 내는 데는 충분했던 것 같다.)