Two Sum

https://neetcode.io/problems/two-integer-sum/question

문제 파악

주어진 배열에서 두 개의 서로 다른 원소를 골라 합이 target이 되게 하고, 그 원소들의 인덱스를 반환함

중요한 조건은 반드시 정답은 하나만 존재하고, 같은 원소는 두번 사용하면 안됨 (i!=j), 결과는 작은 인덱스부터 반환함.
즉, 값(value)가 아니라 인덱스(index)를 찾는 문제

문제의 핵심

숫자 x 가 있을 때, 이전에 target-x를 본적이 있으면 정답

사고 흐름

처음에 target-x를 생각하긴 했지만 첫 구현은 Brute Force로 풀었음. 배열을 이중 순회해서 선형 탐색함

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 2:
            return [0,1]

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

i를 0부터 순회해서 target-nums[i]를 계산하고 찾으면 즉시 반환함. 바깥 루프와 안쪽 루프 모두 O(n) 시간복잡도가 걸려서 총 시간복잡도는 O(n^2). 공간복잡도는 추가 메모리 사용하지 않아서 O(1)

입력 크기 (<_1000)에서는 충분히 통과하지만, 대규모 입력에서는 비효율적인 코드임.

그래도 early stop을 생각해서 nums가 두개 라면 바로 해당 nums를 반환. 그러나 조건이 없어도 아래 로직에서 자동으로 처리 되기 때문에 일관성을 깨서 제거하면 좋은 코드.

개선

여기서 핵심적으로 사용해야 하는 ADT는 Hash Table(Dictionary)
: 여기서 의도된 건 Hash Table 활용 능력을 보는 대표 문제임
Hash Table을 사용하면 평균 탐색 O(1)임.
순회는 한번만 하면 되므로 시간복잡도는 O(n), 그대신 공간복잡도는 O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 2:
            return [0,1]

        tmp_dict = {}

        for i in range(len(nums)):
            if nums[i] not in tmp_dict:
                tmp = target-nums[i]
                tmp_dict[tmp] = i
            else:
                return [tmp_dict[nums[i]], i]

이렇게 풀었는데.. enumerate 를 사용해서 좀 더 가독성있게 표현 가능

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}

        for i,v in enumerate(nums):
            diff = target-v
            if v in seen:
                return [seen[v], i]

            seen[diff] = i

가독성 및 파이써닉한 측면에서 위와 같이 개선함.
시간복잡도와 공간복잡도 모두 O(n)