[python] LeetCode #1 - Two Sum

출처 : LeetCode, https://leetcode.com/problems/two-sum/ 

Two Sum - LeetCode

 

회사 분의 추천으로 리트코드를 시작해보았다.

문제가 영어라 내 해석에 확신을 가질 수 없다.........

 

이제 더 이상 백준에서 건드려볼 수 있는 문제들이 남지 않아서

스피드런은 힘들 것 같다........

 

파이썬은 새로운 알고리즘을 뚫는 용도로 사용하고, JS로 언어를 바꿀 준비를 해야할 듯 하다.

 

 

먼저, 생각해야 할 부분

 

1. 가장 빨리 떠올릴 수 있는 풀이의 시간 복잡도는 O(N^2)이다.

    이보다 더 빨리 할 수 있다!

 

---

 

내 풀이

 

from collections import defaultdict

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        
        nums_dict = defaultdict(lambda: list())
        
        for i in range(length):
            nums_dict[nums[i]].append(i)
            
        nums_dict = dict(sorted(nums_dict.items(), key=lambda x:x[0]))
            
        for key, value in nums_dict.items():
            if target - key in nums_dict:
                if target - key == target//2:
                    return value
                else:
                    return [value[0], nums_dict[target - key][0]]

 

더 짧은 풀이를 생각해보라길래 어떻게든 사전 자료형을 써서 검색 시간을 줄여보겠다고 생각했는데

이 풀이의 시간 복잡도는 sort 함수 때문에 O(NlogN)이다.

 

사전 자료형으로 검색 시간을 O(1)로 줄이고, 이를 통해 절반만 보겠다는 접근 자체는 나쁘지 않았다.

다만 답이 무조건 있다는 조건 하에 target//2인 숫자가 1개만 있을 경우를 대비해

정렬을 해서 target//2인 숫자를 가장 마지막에 탐색해 따로 처리하겠다는 생각을 했는데

굳이 정렬하지 않고도 바로 알 수 있더라.

 

---

시간 복잡도

O(NlogN)

 

알게 된 점

 

- O(N) 풀이

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = dict()
            
        for index in range(len(nums)):
            num = nums[index]
            try:
                return [nums_dict[target -num], index]
            except:
                nums_dict[num] = index

 

원리는 간단하다. 사전 자료형에서 target - num이 있는지 검색하고,

없다면 target-num을 키로, index를 value로 사전에 넣는다.

 

이렇게 되면 list를 순회하면서 사전에 target-num이 있다면, 바로 그 값과 현재 index를 return하면 되고,

target // 2인 숫자가 1개만 있어도 이를 다시 검색할 일이 없기 때문에 넘어가서 정상적인 답이 도출된다.

 

고찰

 

-

 

Github

LeetCode #1 - Two Sum

 

Reference

Two Sum - Leetcode #1 Short & Simple Solution