[LeetCode] 1. Two Sum

1. 문제 이해

문제 해석

integers가 담긴 list nums와 integer target을 입력 받고,
nums의 2개 요소 합이 target과 같아질 때,
2개 요소의 index를 담은 list를 반환한다.

제약 조건 해석

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

• 시간복잡도로 측정될 값은 nums.length이다.
  10^4 이하 까지 범위가 정해져있으므로 O(n^2)의 복잡도만 되어도 위험, O(nlogn) 까지가 안전하다.
• nums[i], 요소 1개의 최댓값은 1,000,000,000 이고,
  2개의 요소가 최댓값일지라도 그 합이 int 자료형 표현 범위인 2^31(2,147,483,648) 보다 작으므로 제약 조건 내에서 문제는 없다.
• target 또한 int 자료형 표현 범위 안에 있다.

2. 접근 방법

먼저 직관적으로 생각하기

이중 반복문으로 완전탐색 후 두 요소를 찾아 배열에 담아 리턴하는 방법이 먼저 떠올랐지만
nums.length 제약 조건에 아슬하게 걸릴 것 같아 nums의 각 요소의 '값: idx' pair를 Dicionary에 담고
nums를 오름차순 정렬한 list를 순회하며, 그 합이 target과 같은 2개의 요소를 찾기로 했다.

활용한 자료구조 & 알고리즘

• Dictionary 자료형을 활용한 Hash table

메모리 사용

We can reduce the lookup time from O(n) to O(1) by trading space for speed.
A hash table is well suited for this purpose because it supports fast lookup in near constant time.

실제 문제를 푸는 단계에서는 시간복잡도를 줄이기 위해서 메모리를 사용하겠다는 개념을 갖고 있지는 않았다.
LeetCode Official Solution을 보면서 메모리를 사용해 시간복잡도를 낮추는 trade-off 관계를 다시 상기했다.

3. 코드 설계 및 구현

작성한 코드

class Solution(object):
    def twoSum(self, nums, target):
        # 1. 오름차순 정렬
        sortedNums = sorted(nums)
        lastIdx = len(sortedNums) - 1 
        numsDict = {}

        # 2. 딕셔너리에 nums 요소의 값: 인덱스 쌍을 순차적으로 추가
        for idx in range(lastIdx + 1):
            numsDict[nums[idx]] = idx

        # 3. nums[len-1] 부터 target 보다 작은 값을 찾고,
        # 해당하는 값의 idx를 lastIdx에 할당 
        for idx in range(lastIdx, 0, -1):
            if sortedNums[idx] < target:
                lastIdx = idx
                break
        # 4. lastIdx가 0 보다 크면 
        if lastIdx > 0:
            for idx in range(lastIdx):
                maximum = sortedNums[lastIdx]
                curEl = sortedNums[idx]
                curVal = target - maximum
                # target - nums[lastIdx] 에 해당하는 수가 있다면 
				# numsDic에 저장된 원래의 idx를 list에 담아 리턴
                if curEl == curVal:
                    origin1 = numsDict[curEl]
                    origin2 = numsDict[maximum]
                    return [origin1, origin2]

                # 없다면 lastIdx를 하나 줄인다.
                lastIdx = lastIdx - 1
        return

• nums의 요소 중 최댓값이면서 target 보다는 작은 수의 index를 lastIdx로 두고,
  뒤에서 부터 하나씩 idx를 줄여가면서 그 다음 최댓값과 더해질 요소를 맨 앞부터 순회하면서
  그 값을 찾았다면 dictionary에 저장되었는지 확인하고 value와 함께 저장된 idx를 조회한다.
• Greedy 알고리즘을 구현했던 것이 떠올랐는지 오히려 더 복잡해졌다.
• 결과적으로 값이 같은 2개의 요소가 입력될 경우를 처리하지 못했다.

One-pass Hash table(O(n))

class Solution(object):
    def twoSum(self, nums, target):
    	# Hash table로 사용할 dict 미리 선언
        hashmap = {}
        # nums 순회
        for i in range(len(nums)):
        	# target - 현재 조회중인 값이 Hash table에 있다면
            # 해당 idx와 현재 조회중인 idx를 list에 담아 리턴한다.
            complement = target - nums[i]
            if complement in hashmap:
                return [hashmap[complement], i]
            # (찾고 있는 값이 Hash table에 없었다면)
            # 현재 조회중인 값을 key, idx를 value로 추가한다.
            hashmap[nums[i]] = i

• Hash table을 만들어 추가적인 메모리를 사용하지만
  O(n)복잡도로 감소했다.
• nums의 요소를 순회하며 Hash table에 data를 넣으면서,
  구하고자 하는 값이 이미 Hash table에 있는지 확인할 수 있게 되었다.

Reference: https://leetcode.com/problems/two-sum/solutions/127810/two-sum/