[Python] List <두 수의 합>

선형 자료구조를 다루는 가장 기초적인 문제로, 리트 코드의 1번 문제라서 한번 가져와 봤다.

문제는 단순 비교하여 값을 리턴한다고 구성하면 아마 초등학생도 풀 수 있는 정도의 난이도의 문제이지만, 의외로 최적화할 수 있는 방법이 많아서 다뤄보려고 한다.

---

1. 무차별 대입 방식

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]


if __name__ == '__main__':
    nums = [2, 5, 7, 9]
    target = 9
    print(twoSum(nums, target))

2중 for 문을 만들어서 단순 비교를 하는 방식으로 풀 수 있으나, 이 방식은 이중 for문을 사용하기 때문에 속도 측면에서 상당히 비효율적이라고 할 수 있다. 

 

---

2. target 에서 현재 인덱스의 value 를 빼고, in 연산자를 사용

 

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target - n

        if complement in nums[i+1:]:
            return [nums.index(n), nums[i+1:].index(complement) + (i + 1)]


if __name__ == '__main__':
    nums = [2, 5, 7, 9]
    target = 9
    print(twoSum(nums, target))

target - n 값이 나머지 배열에 존재하는 지 여부를 판단하여 결과를 도출하는 방식이다. in 연산은 for문과 시간 복잡도가 동일하지만, in 연산자는 상수항 연산을 생략하기 때문에 훨씬 빠르다고 할 수 있다. 또한 열거형 사용도 시간 복잡도를 줄이는 데 도움을 준다.

 

---

3. 딕셔너리 이용

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    nums_map = {}
    # 키와 값을 바꿔서 딕셔너리로 저장
    for i, num in enumerate(nums):
        nums_map[num] = i

    # target 에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
        if target - num in nums_map and i != nums_map[target - num]:
            return [i, nums_map[target - num]]


if __name__ == '__main__':
    nums = [2, 5, 7, 9]
    target = 9
    print(twoSum(nums, target))

dnums의 index와 value를 바꿔서 저장하고 있는 map을 하나 만들어서 target-n을 key로 가지고 있고, n과 target-n의 인덱스 값이 동일하지 않은 경우에 해당 인덱스 값들을 바로 반환하도록 하면, 시간 복잡도를 훨씬 더 줄일 수 있다.