[파이썬 알고리즘 인터뷰] 6. 두 수의 합

https://github.com/onlybooks/algorithm-interview

GitHub - onlybooks/algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는

1. 문제

leetcode 1. Two Sum

정수형 배열 nums와 정수 target을 입력받아 target을 만들 수 있는 배열의 두 인덱스 값을 리턴하라

 

2. brute force

가능한 모든 조합을 더해서 target과 일치하는지 확인하는 방법이다. O(n^2)의 시간복잡도를 가진다.

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]

 

3. in을 이용한 탐색

모든 배열의 요소 num에 대해서 target - num이 배열에 존재하는지 in 연산을 이용해 확인하는 방법이다. 2번과 시간복잡도는 O(n^2)으로 같지만 직접 값을 더하고 비교하는 것보다 내부 함수로 구현된 in 연산을 사용하는 것이 더 빠르다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, num in enumerate(nums):
        n = target - num
        if n in nums[i + 1:]:
            return [i, nums[i + 1:].index(n) + i + 1]

 

4. 딕셔너리 이용하기

이 방법은 딕셔너리의 키/값 조회를 이용한 방법이다. 기존의 nums 배열의 값들을 key, 배열의 순서를 value로 하는 딕셔너리를 새로 만든다. 그리고 타겟에서 nums의 값들을 뺀 수를 key로 딕셔너리를 조회한다. 딕셔너리는 해시테이블로, 평균적으로 O(1)에 조회회가 가능하다. 이 방법은 총 O(n)의 시간복잡도를 가진다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    #딕셔너리 만들기
    dict = {}
    for i, num in enumerate(nums):
        dict[num] = i

    #타겟에서 첫번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
        if target - num in dict and dict[target - num] != i:
            return [i, dict[target - num]]

이번 문제를 풀면서 간단해보이는 문제도 정말 다양한 방법을 이용해 풀 수 있다는 것을 알게 되었다. 문제를 풀면서 더 효율적인 자료구조/알고리즘을 고민해봐도 좋을 것 같다.