[파이썬 알고리즘 인터뷰] - 7장 (배열)

 

 

 

 

 

 

 

 두 수의 합

 

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

 

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

 

- 출력 => [0,1]

 

 

 

 

 

 

 풀이 1 : 브루트 포스(Brute Force)

 

- 모든 경우를 전부 탐색한다.

 

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

 

- O(N^2)의 속도

 

 

 

 

 

 

 풀이 2 : in 연산 사용

 

- in을 이용한 탐색

 

def solution(nums:list, target:int) -> list:
    for i, val in enumerate(nums):
        complement = target - val
        if complement in nums[i+1:]:
            return i, nums[i+1:].index(complement) + (i+1) 
            # nums에서 전체 검색을 하는 index가 아니라 찾은 곳에서 index를 찾고 다시 i+1을 더함

 

- Brute Force와 같은 O(N^2)이지만 연산 속도는 풀이 1보다 훨씬 빠르다. O 표기법으로 표현 되지 않는 속도 차이가 존재한다.

 

 

 

 

 

 

 풀이 3 : 딕셔너리 사용

 

def solution(nums:list, target:int) -> list:
    nums_maps = {}
    for i, val in enumerate(nums): # val를 key, index를 value로 딕셔너리 
        nums_maps[val] = i
    for i, val in enumerate(nums):
        if target-val in nums_maps and i != nums_maps[target-val]:
            return i, nums_maps[target-val]

 

- 타겟에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다. 그렇다면 두 번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔서 딕셔너리로 저장하면 나중에 두 번째 수를 키로 조회해서 정답을 즉시 찾아낼 수 있다. 

 

- O(N) 

 

 

 

 

 

 

 

 풀이 4 : 풀이 3의 딕셔너리 2개를 1개로 합치기

 

def solution(nums:list, target:int) -> list:
    nums_map = {}
    for i, val in enumerate(nums):
        if target-val in nums_map:
            return [nums_map[target-val], i] 
            # 이미 존재한다는 것은 더 작다는 의미이므로 i가 뒤에 나온다.
        nums_map[val] = i
 

 

- for문을 하나로 만들어 우선 검사하여 존재하는지 보고, 없을 경우 dict에 내용을 추가한다.

 

- 속도 차이는 풀이 3과 거의 차이가 없지만 보기에 간결하다.

 

 

 

 

 

 

 

 풀이 5 : 투 포인트(two points)

 

- 이 문제를 투 포인트로 접근한다면 풀이가 가능하지만 전제조건은 배열이 정렬되어 있어야 한다는 것이다. 배열이 정렬되어있지 않다면 정렬을 우선한다.(O(NlogN)). 문제가 인덱스가 아니라 해당 값을 찾는 것이라면 당연히 이를 통해 해결 가능하다. 하지만 이 문제는 index를 찾는 것이므로 정렬하는 순간 인덱스가 바뀌어 문제가 생긴다. 물론 인덱스를 포함한 튜플 리스트를 만들어 정렬하여 할 수도 있지만 위에 방법보다 느리다.