1. 문제

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

2. 풀이

2.1. 브루트포스

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

가장 단순하게 떠올릴 수 있는 방법이다. 한 원소(nums[i])와 다른 원소(nums[j])의 합이 target과 같을 때까지 탐색한다. 순차적으로 반복되는 이중 for문으로, $O(n^2)$의 시간 복잡도를 갖는다.

2.2. in을 이용한 탐색

class Solution:
    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)]    

nums 의 각 원소에 대해 target의 보수를 구한 후 그 보수가 nums에 존재하는지 in으로 탐색한다. nums의 원소를 순차적으로 탐색하는 for문의 시간 복잡도는 $O(n)$이고 각 반복에 대해 in으로 탐색할 때 $O(n)$의 시간 복잡도를 가지므로 전체 시간 복잡도는 $O(n^2)$가 된다. 브루트포스 풀이와 시간복잡도는 같지만 이 풀이가 훨씬 빠르다. 같은 시간복잡도를 갖더라도 for문을 사용한 탐색보다 python 내장 함수로 구현된 탐색이 더 빠르기 때문이다.

2.3. key를 이용한 탐색

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

        for i, n in enumerate(nums):
            complement = target - n

            if complement in nums_dict:
                return [nums_dict[complement], i]
            
            nums_dict[n] = i

보수를 순차적으로 구한다는 점은 2.2. 와 같다. 다른 점은 리스트가 아니라 딕셔너리에서 보수를 탐색한다는 점이다. in으로 값을 탐색하는 것은 리스트에서 $O(n)$의 시간복잡도지만 딕셔너리에선 $O(1)$의 시간복잡도를 갖는다. 따라서 전체 시간복잡도는 $O(n)$이 된다.