[배열] 두 수의 합

문제

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

• 입력

nums = [2, 7, 11, 15], target = 9

• 출력

[0, 1]

• 설명
  nums[0] + nums[1] = 2 + 7 = 9
  따라서 0, 1을 리턴한다.

풀이

브루트 포스(Brute-Force)

브루트 포스 : 모든 조합을 더해서 일일이 확인하는 방법

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]

이 경우 시간 복잡도는 O(n**2)로 지나치게 느리다.

in을 이용한 탐색

target - n이 존재하는지 탐색하는 문제로 변경한다.
in의 시간 복잡도는 O(n)이고, 따라서 전체 시간 복잡도는 이전과 동일한 O(n**2)이지만 같은 시간 복잡도라도 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 nums.index(n), nums[i + 1:].index(complement) + (i + 1)

첫 번째 수를 뺀 결과 키 조회

딕셔너리는 해시 테이블로 구현되어 있고, 분할 상환 분석에 따른 시간 복잡도는 O(1)이며, 전체는 O(n)이 된다.
키와 값을 바꿔서 딕셔너리로 저장해두면, 타겟에서 첫 번째 수를 뺀 결과를 키로 조회해서 정답을 즉시 찾을 수 있다.

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 nums.index(num), nums_map[target - num]

조회 구조 개선

위와 성능상의 차이는 없지만 코드를 더 간결하게 만들 수 있다.

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

투 포인터 이용

투 포인터 : 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크다면 오른쪽 포인터를 왼쪽으로, 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식
투 포인터의 시간 복잡도는 O(n)이다.

결론부터 말하자면 투 포인터로는 풀 수 없다.
nums가 정렬된 상태가 아니고, 정렬 로직을 추가하게 되면 인덱스는 모두 엉망이 되기 때문에 원래 인덱스를 찾을 수 없다.

소스 코드