LeetCode | 001. Two Sum

문제

nums 리스트 안의 요소 중 더해서 target이 되는 두 수의 인덱스를 리스트로 리턴.

- 답은 하나만 존재하고, 요소를 중복해서 사용하지 않는다.

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

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

 

내 풀이

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
# Runtime: 6319 ms, faster than 10.71% of Python online submissions for Two Sum.
# Memory Usage: 14.3 MB, less than 67.72% of Python online submissions for Two Sum.

코드카타때 풀었던 방식대로 이중포문을 사용해서 풀었다. 

 

다른 풀이1

def twoSum(self, nums, target):
        for i, value in enumerate(nums):
            remaining = target - value
            nums[i] = None
            if remaining in nums:
                return [i, nums.index(remaining)]
# Runtime: 1190 ms, faster than 42.52% of Python online submissions for Two Sum.
# Memory Usage: 14.2 MB, less than 67.72% of Python online submissions for Two Sum.

서로 다른 수를 더해야 해서 인덱스를 두개로 나누느라고 for문을 두번 돌렸는데

target-value를 해서 그 수가 리스트에 있는지를 판단하면 포문을 한번만 돌려도 된다.

 

nums[i]의 값을 None으로 바꿔주는 이유는 같은 값을 두번 리턴할 수 있기 때문.

저 부분이 없으면 Input: nums = [3,2,4], target = 6의 경우에 [1, 2]가 아닌 [0, 0]이 리턴된다.

값을 지우지 않고 None으로 바꿔주는건 인덱싱에서 문제가 있을수 있기 때문!

원래 이런 경우 for문에는 nums의 복사본을 돌리고 nums에서는 해당값을 지우는 방법으로 했는데 이런 방법도 있다는걸 알았다!

for i in nums[:]:
    ...
    nums.remove(nums[i])
    ...

(이 문제에선 마지막에 해당 값의 인덱스를 반환해야 하기 때문에 nums에서 이렇게 하면 안될듯!)

 

다른풀이2

seen = {}
    for i, value in enumerate(nums):
        remaining = target - nums[i]   
        if remaining in seen:
            return [i, seen[remaining]]           
        seen[value] = i 
# Runtime: 82 ms, faster than 68.17% of Python online submissions for Two Sum.
# Memory Usage: 14.2 MB, less than 85.62% of Python online submissions for Two Sum.

https://www.code-recipe.com/post/two-sum

 

82ms.....무슨일

해시맵을 이용한 풀이라고 하는데 해시맵은 키-밸류를 가진 자료구조라고 한다.
그래서 파이썬에서는 딕셔너리가 해시테이블로 구현돼있다고 한다.
리스트는 순차적으로 값을 찾아가고 해시는 자료의 주소값을 알아내서 바로 찾아간다고 한다.

 

위에서는 nums에 남아있는 값이랑 찾을 값을 비교했는데 nums는 리스트이기 때문에 for문을 돌리지 않았어도 값을 찾을때 순차적으로 비교를 해서 속도가 느려졌다.

여기서는 한번 본 값을 딕셔너리에 인덱스:값으로 저장하고 찾을값을 남은 리스트에서 찾는게 아니고 딕셔너리에 있는 이미 본 값이랑 비교했다.

그래서 순차적인 조회는 for문에서 진짜로 한번만 돈거고 딕셔너리에서는 순차조회를 안하니까 시간절약이 많이됐나보다

 

for문을 한번쓴다고 진짜 한번만 도는게 아니구나^^.....

그리고 나처럼 포문 두개돌린건 최악의 방법이라고 한다^^

자료구조의 중요성...열심히 공부해야겠다^^!