[파이썬 알고리즘 인터뷰] 두 수의 합

Two Sum - LeetCode

나의풀이

def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer=[]
        for i in range(len(nums)-1):
            if (target-nums[i]) in nums[i+1:]:    
                answer.append(i)
                answer.append(nums[i+1:].index(target-nums[i])+(i+1))
        return answer

in을 사용하여 target을 만족시키는 다른 값이 존재하는지 확인하는 코드를 작성하였다. 하지만 이는 뒤에서 살펴보겠지만 브루트포스에 비해 훨씬 나은 성능을 보이지만 in 역시 O(n)의 시간복잡도가 소모 되므로 O(n²)의 시간복잡도를 보인다.

브루트포스로 계산

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

브루트포스 알고르즘은 말 그대로 모든 경우의 수를 고려하여 target을 만족시키는 값을 찾는 것이다. 나의 풀이법과 비슷하지만 실행시간을 비교해보면 약 6배정도 차이가 난다.

in을 이용한  탐색

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i,n in enumerate(nums):
        complement = target - n

        if complement in nums[i+1:]:
            return [i,nums[i+1:].index(complement)+(i+1)]

나의 알고리즘과 같은 논리로 작성된 코드이며 enumerate와 반드시 한쌍의 닶이 존재한다는 점을 이용하여 더욱 깔끔하게 작성된 것을 볼 수 있다.

첫 번째 수를 뺀 결과 키 조회(해쉬함수)

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map={}

    for i,num in enumerate(nums):
        nums_map[num]=i
    
    for i,num in enumerate(nums):
        if target - num in nums_map and i != nums_map[target-num]:
            return [i,nums_map[target-num]]

• value in dict를 사용하여 value가 dict의 key로 존재하는지 확인할 수 있다. 

값을 키로 인덱스를 값으로 하여 딕션너리를 작성하고 이를 바탕으로 target을 만족시키는 값을 바로 찾는 방법이다. 이는 분할 상환 분석에 따르면 O(1)의 복잡도를 보이며, 전체  O(n)이 된다. 이는 앞선 풀이들에 비해 20배나 빠른 성능을 보여준다. 

자료 구조 개선

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map={}
    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target-num], i]
        nums_map[num]=i

이는 앞선 해쉬를 사용한 풀이에서 두개의 for문을 사용하는 대신 하나의 for문으로 합친 풀이법으로 앞선 방법과 성능상의 큰차이는 없으나 훨씬 간결하니 보기 좋다.