Two Sum

반응형

문제 링크 : leetcode.com/problems/two-sum/

Two Sum - LeetCode

릿트코드를 하면 처음 풀어본다는 가장 쉬운 문제다.

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로 풀게되서 굉장히 손해를 많이 보는 코드가 되었다.

저작자표시비영리동일조건