[Leetcode] two-sum

1. 개요

 

숫자 배열 nums과 목표 숫자 target 하나가 주어집니다.

숫자 배열에 있는 숫자 두 개를 더해서 목표 숫자를 만들고,

각 숫자의 인덱스를 배열로 반환해야 합니다.

예를 들어,

[1, 2, 3] 과 5가 주어진 경우

2 + 3 = 5 이므로, [1, 2]를 반환해야 합니다.

문제의 정답은 반드시 존재합니다.

 

2. 단순 무식한 방법

 

이중 루프를 돌면서 리스트에서 두 개의 숫자를 골라 더해보는 방법이 있습니다.

쉽고 간단한 대신 O(n^2)의 시간 복잡도를 가집니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            for j, m in enumerate(nums):
                if n + m == target and i != j:
                    return [i, j]

 

3. 머리를 좀 쓴 방법

 

이번에는 이중루프를 도는 대신, 하나의 반복문 안에서 n과 짝을 이루는 m의 인덱스를 찾는 방법입니다.

이것도 O(n^2)의 시간 복잡도를 가지지만 m의 index를 빨리 찾을 경우 위의 코드보다는 빠른 속도로 해결이 가능합니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            m = target - n
            try:
                j = nums.index(m)
            except ValueError:
                continue
            if i != j and j >= 0:
                return [i, j]

 

4. 최적의 해

 

O(n) 시간에 해결하는 방법이 있습니다.

3번에서는 m의 인덱스를 찾는데 최악의 경우 nums의 길이만큼의 시간이 걸리는 것이 문제였습니다.

아래와 같이 딕셔너리에 각 숫자의 인덱스를 저장해두면 상수 시간 안에 인덱스를 찾을 수 있습니다.

 class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	seen = {}
        for i, n in enumerate(nums):
            m = target - n
            if m in seen: # 딕셔너리에 m이 저장되어 있는 경우 그 인덱스를 사용
                return [seen[m], i]
            seen[n] = i # 딕셔너리에 n과 그 인덱스 i를 저장한다.