[파이썬 알고리즘] 두 수의 합

두 수의 합

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

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

출력
[0, 1]

---

가장 간단한 풀이 방법인 브루트 포스에서 시작해서 여러 풀이를 비교하며 파이썬의 선형 자료구조를 다루는 법을 익히자.

방법1. 브루트 포스

code: twoSum1.py

리스트를 이중 포문으로 검사하며 리스트 안의 모든 두 숫자를 더한 결과를 탐색하며, target과 같아지면 해당 인덱스 값을 리턴한다.

def twoSum(nums, target):
    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. in을 이용한 탐색

code: twoSum2.py

타겟에서 첫 수를 뺀 값이 입력된 배열에 존재하는지 확인하는 방법으로 탐색에 필요한 시간을 줄일 수 있다.

def twoSum(nums, target):
    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)]

여기서 in의 시간 복잡도는 O(n)이며, 전체 시간 복잡도는 이전의 풀이와 같은 O(n^2)이다. 하지만, 같은 시간 복잡도라도 in 연산이 훨씬 가볍고 빠르다.

방법3. 첫 번째 수를 뺀 결과 키 조회

위의 풀이를 약간 비틀어 먼저 값과 그 인덱스를 딕셔너리에 저장해 둔 뒤, 뺀 결과를 해당 딕셔너리에서 조회하면 필요없이 이터레이션하지 않고 값을 찾을 수 있다.

def twoSum(nums, target):
    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 [i, nums_map[target - num]]

딕셔너리는 해시 테이블로 구현되어 있고, 조회는 평균적으로 O(1)에 가능하다.

방법4. 조회 구조 개선

위 풀이에서는 딕셔너리에 저장과 조회를 두번의 for문을 통하여 처리했지만, 이를 개선하여 하나의 for문으로 합칠 수 있다.

성능상의 큰 이점은 없지만, 코드가 좀더 깔끔해진다.

def twoSum(nums, target):
    nums_map = {}

    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], i]
        nums_map[num] = i