1. 문제 소개
- 배열, 해시 테이블을 이용해야 하는 문제에 속한다.
- leetcode 에서도 난이도 easy 수준의 문제다.
- 최근 블라인드에 이 문제에 대한 이야기가 인기글로 올라와서, 풀어봤다.
2. 코드
#Runtime: 60 ms, faster than 83.47% of Python3 online submissions for Two Sum.
#Memory Usage: 15.3 MB, less than 42.38% of Python3 online submissions for Two Sum.
class Solution:
# Brute Force - 가장 단순한 접근 -> time complexity : (n2), space complexity : o(1)
def twoSum(self, nums,target):
target_indices = []
for i in range(0,len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
target_indices+=[i,j]
return target_indices
return target_indices
# Two - pass Hash Table -> time complexity : (n), space complexity : o(n)
def twoSum(self, nums,target):
hash_map = {}
target_indices = []
# 자료구조를 해시 맵으로 생성
for idx,va in enumerate(nums):
hash_map[va]=idx
# look up
for idx,va in enumerate(nums):
minus_value = target - va
if minus_value in hash_map and hash_map[minus_value] != idx:
target_indices+=[idx,hash_map[minus_value]]
break
return target_indices
# One pass hash Table -> time complexity : (n), space complexity : o(n)
def twoSum(self, nums,target):
hash_map={}
for idx,va in enumerate(nums):
minus_value = target-va
if minus_value in hash_map:
return [idx,hash_map[minus_value]]
hash_map[va]=idx
def test(self):
nums = [2,1,94,3,-2]
target = 92
result = self.twoSum(nums,target)
print(result)
if __name__ == '__main__':
s = Solution()
s.test()
3.코멘트
- 난 첫 번째 Brute Force 라고 부르는 방식으로 문제를 풀었다. (심플한 방법을 제일 좋아하기도 하고, 저 방법이 가장 먼저 떠올랐다. )
- leetcode는 문제 제출에 대한 피드백이 비교적 잘 되있다. (시각화나, 해설, discussion도 있고..)
- 첫 번째 방식보다, 해시 기반의 자료구조를 이용했을때 시간복잡도가 매우 낮았다.
- 해시 맵을 만드는 방법도 생각을 안 한건 아니었지만, 해시 맵을 만든다고 하더라도, nums 배열의 full scan 비용 * 해시 맵 안에서 key 를 scan 비용을 더 하면 O(N2) 이 될거라고 생각했는데 아니었다. (해시 맵안에서는 키를 순회하는게 아니라 맵에 키가 있는지만 보면 되니까.. -_-; )
- Hash를 이용하면 Lookup 시간을 O(n) 에서 O(1)로 줄일 수 있다.
