[LeetCode] 1. Two Sum (Python)

LeetCode를 문제 번호 순서대로 풀지는 않지만, 1번 문제는 나름의 상징성이 있다고 생각해서 풀이를 남겨봅니다.

 

leetcode.com/problems/two-sum/

Two Sum - LeetCode

---

풀이 1. Brute Force

from typing import List

def twoSum(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]

매우 단순하게 모든 경우의 수를 확인하는 방법은, 시간복잡도가 당연하게도 O(n^2)입니다.

 

풀이 2. using in

from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:
    for idx, num in enumerate(nums):
        if target - num in nums[idx+1:]:
            return [idx, nums[idx+1:].index(target - num) + idx+1]

제가 처음 생각한 풀이입니다. 숫자에는 중복이 있을 수도 있고 target - num == num인 경우도 있어서 nums[idx+1:]에 대해 in 검사를 해줘야 합니다. 풀이 1보다 5배 정도 빠르지만, in의 시간복잡도가 O(n)이기 때문에 시간복잡도는 여전히 O(n^2)입니다.

 

풀이 3. using dictionary (hash table)

from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:
    hash_table = {}
    for idx, num in enumerate(nums):
        hash_table[num] = idx
    
    for idx, num in enumerate(nums):
        if target - num in hash_table and hash_table[target - num] != idx:
            return [idx, hash_table[target - num]]

파이썬의 딕셔너리를 사용해 숫자와 인덱스를 각각 키와 값으로 저장해 두면, 타겟에서 첫 번째 숫자를 뺀 값의 인덱스를 찾는 수고를 덜 수 있을 것입니다. 숫자에 중복이 있는 경우에도 답을 찾는 데는 문제가 되지 않습니다. 시간복잡도는 O(n)입니다.