[NeetCode/Python] Two Integer Sum

문제 링크:

https://neetcode.io/problems/two-integer-sum

NeetCode

 

합이 타겟이 되는 두 수를 찾는 문제다. 반드시 한 쌍의 숫자만 타겟 숫자를 만들 수 있다.

 

 

[나의 풀이]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            pair = target - nums[i]
            for j in range(i + 1, len(nums)):
                if nums[j] == pair:
                    return [i, j]

        return []

간단하게 이중 for문으로 합을 구하도록 했다.

 

[솔루션 풀이]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

 

 

내 풀이와의 차이점은 그거다

나는 이중 for문으로 현재 숫자와 그 이후의 숫자의 합을 찾으려 했다면,

솔루션은 현재 숫자와 그 이전의 숫자의 합을 찾으려 한 것이다. 그래서 이전 숫자들을 prevMap에 따로 index와 매핑해두었다.

사실 시간 복잡도는 비슷하지만(in의 시간 복잡도도 O(n)), 뭔가 코드 적으로 훨씬 깔끔해 보인다.

 

이런 흐름의 전환은 다시금 익혀야할 부분이다!

 

시간 복잡도

최악의 경우 O(n^2)

참고: https://wiki.python.org/moin/TimeComplexity