[Python, Algorithm] 두 수의 합

출처: 파이썬 알고리즘 인터뷰

 

info

> enumerate()

> 인자의 index와 값을 튜플 형태로 전달

 

for i, n in enumerate(li):
    print(i, n)

for tu in enumerate(li):
    print(tu)

print:

1 a
2 b
3 r
4 1
5 d
(0, 3)
(1, 'a')
(2, 'b')
(3, 'r')
(4, 1)
(5, 'd')

 

 

방법 1) brute-force 방법

모든 조합 조회 ( O(n^2) )

def two_sum_bruteForce( nums : [int], target : int) -> [int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]

 

방법 2) in 찾기

target - n 이 존재하는지 찾는 방법 ( O(n)

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

 

방법 3) key 조회

키와 값을 바꿔서 저장 후 조회

def two_sum_key(nums : [int], target : int ) -> [int]:
    num_map = {}
    for i, n in enumerate(nums):
        num_map[n] = i

    for i, n in enumerate(nums):
        if target - n in num_map and i != num_map[target - n]:
            return nums.index(n), num_map[target - n]

 

for문 하나로 통일

def two_sum_key2(nums : [int], target : int ) -> [int]:
    num_map = {}
    for i, n in enumerate(nums):
        if target - n in num_map:
            return [num_map[target - n ] , i]
        num_map[n] = i

 

 

방법 4) 투 포인트 이용

이 방법은 정렬이 되어 있을 때 가능하다.

타겟을 찾을 때는 좋은 방법이지만, 인덱스를 찾아야 한다면 비효율적이다.

def two_sum_twoPoint( nums : [int], target : int) -> [int] :
    left, right = 0, len(nums) - 1

    while not left == right:
        if nums[left] + nums[right] < target :
            left += 1
        elif nums[left] + nums[right] > target:
            right -= 1
        else:
            return left, right