Problem

Solution

1) 브루트 포스로 계산

브루트 포스(Brute-Force) : 배열을 2번 반복하면서 모든 조합을 더해서 일일히 확인해보는 무차별 대입 방식

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)): # 리스트 iteration
            for j in range(i + 1, len(nums)): # 리스트의 두 번째 요소부터 iteration
                if nums[i] + nums[j] == target: # 리스트의 각 요소 중 target과 같은 값이면
                    return [i, j] # 해당하는 index return

지나치게 느린 비효율적인 풀이로 이 경우 풀이 시간 복잡도는 $O(n^2)$.

2) in을 이용한 탐색

모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색하는 방식으로 접근

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 [nums.index(n), nums[i + 1:].index(complement) + (i + 1)] # 현재 반복 이후 리스트에서 비교했으니 (i + 1)을 더해 입력 리스트의 인덱스를 추출한다. 

in의 시간 복잡도는 $O(n)$, 따라서 전체 시간 복잡도는 이전과 동일한 $O(n^2)$.
하지만 같은 시간 복잡도라도 in 연산 쪽이 훨씬 더 가볍고 빠르다.
상수항이 생략되어 표기된 시간 복잡도에서 생략된 상수항은 1) 풀이에 비해 훨씬 더 작은 값이라고 할 수 있다.

3) 첫 번째 수를 뺀 결과 key 조회

비교나 탐색 대신 한 번에 정답을 찾는 방법

target에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다. 그렇다면 두 번째 수를 key로 하고 기존의 index를 value로 바꿔서 dictionary에 저장해두면, 나중에 두 번째 수를 key로 조회해서 정답을 즉시 찾아낼 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        
        # key와 value를 바꿔서 dictionary로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i
        
        # target에서 첫 번째 수를 뺀 결과를 key로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return [i, nums_map[target - num]]

dictionary는 해시 테이블로 구현되어 있고, 이 경우 조회는 평균 $O(1)$에 가능하다. 최악의 경우에는 $O(n)$이 될 수도 있다.

4) 조회 구조 개선

3) 풀이에서 dictionary 저장과 조회를 2개의 for문으로 처리하였는데 이것을 하나로 통합

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        
        # 하나의 for 문으로 통합
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i

이 경우 전체를 모두 저장할 필요없이 정답을 찾게되면 함수를 바로 빠져나온다.
그러나 두 번째 값을 찾기 위해 어차피 매번 비교해야 하기 때문에 3) 풀이에 비해 성능상의 큰 이점은 없을 것 같다.

5) 투 포인터 이용 (잘못된 접근방식!)

투 포인터로 해당 문제를 접근하면 어떻게 될까?
투 포인터란 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums.sort() # 입력 리스트 정렬
        left, right = 0, len(nums) - 1
        
        while not left == right:
        	# 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로
            if nums[left] + nums[right] < target:
                left += 1
            # 합이 target보다 크면 오른쪽 포인터를 왼쪽으로
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                return [left, right]

이처럼 투 포인터로 구현하면 코드도 간결하고 이해하기 쉽다. 투 포인터의 시간 복잡도도 $O(n)$이고, 불필요한 추가 계산도 필요없어 매우 빠른 속도가 기대된다.

다만 이 문제는 투 포인터로 풀 수 없다!!
왜냐면 입력값 nums가 정렬된 상태가 아니기 때문이다. nums.sort()로 정렬한다고 하더라두 정렬한 index와 입력 리스트의 index가 다르기 때문에 index가 엉망이 된다.
만약 이 문제가 index가 아니라 값을 찾아내는 문제라면, 얼마든지 정렬하고 투 포인터로 풀이할 수 있다. 하지만 이처럼 index를 찾아내는 문제에서는 이렇게 정렬을 통해 index를 섞어 버리면 곤란하다. 원래 index를 찾을 수가 없기 때문이다.