(leetcode 문제 풀이) 1번, Two Sum

leetcode easy 문제 결코 쉽지 않다. 하나의 방법이 있는 것이 아니라 여러 가지 솔루션이 나올 수 있다. 

문제 설명
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.
 
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]
 
조건
2 <= nums.length <= $10^3$
$-10^9$ <= nums[i] <= $10^9$
$-10^9$ <= target <= $10^9$
Only one valid answer exists.

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

위의 코드는 내가 처음에 짠 코드다. brute force 방식으로 for 문을 2번 쓰기 때문에 시간 복잡도 면에서 불리하다. 메모리 방면에선 괜찮은 수준을 보였다. 

아래는 hash 방식을 사용한 것으로, 나도 enumerate() 까지 썼다가 딕셔너리를 생각하지 못해 다시 지웠다. 딕셔너리를 사용하지 못한 것이 벌써 2번 째다... 

# 참고 모범 코드
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    
        h = {}
        for i, num in enumerate(nums):
            n = target - num
            if n not in h:
                h[num] = i
            else:
                return [h[n], i]

역시 hash를 사용하니 속도 면에서 우월한 성능을 보였다. 

그런데 leetcode 에서 submit을 누르면 Runtime과 Memory Usage를 분석해주던데, 항상 똑같은 결과를 출력하는 것은 아닌 것 같다. 제출할 때마다 상황에 따라 조금씩 차이가 나는데, 2~3ms 차이로 랭킹이 확 바뀌어서 당황했다. 100% 믿지 말고 사람들의 모범 코드도 참고하면서 살펴보자.