문제 링크 : leetcode.com/problems/two-sum/
Two Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
릿트코드를 하면 처음 풀어본다는 가장 쉬운 문제다.
nums(List)와 target 숫자를 받아 nums의 연속된 두 수를 더해서 target을 만들면 그 index 두 개를 return하면 된다.
첫 답안
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, num in enumerate(nums):
second_num = target - num
if second_num in nums and i != nums.index(second_num):
return [i, nums.index(second_num)]
return [None, None]
nums를 순회하면서 타켓에서 순회하는 숫자만큼 뺀 차이가 list에 있는지 찾았다. 메모리도 많이 쓰지만 처리속도가 순위에 보이지 않을정도로 느리다.
Java로 된 Solution을 보니 hash를 써서 풀어야 한다. 가장 star를 많이 받은 답안
class Solution:
def twoSum(self, nums, target):
h = {}
for i, num in enumerate(nums):
n = target - num
if n not in h:
h[num] = i
else:
return [h[n], i]
나는 nums
에 second_num
(답안에서의 n)이 있는지 찾고 그 인덱스를 확인했는데 dict
을 쓰면 n
을 dict
에서 찾고 없으면 바로 dict
에 key
로 현재 num
을 넣고(나중에 n이 num이 될때 꺼내려고) index
를 value
에 넣는다. 그리고 나중에 dict
에 있으면 현재 인덱스와 그 값을 그냥 return
한다.
hash
를 생각 못하니 brutal force
로 풀게되서 굉장히 손해를 많이 보는 코드가 되었다.