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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

• 덧셈으로 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴

 

책에서 구현된 코드

def twoSum(self, nums: List[int], taregt: int) -> List[int]:
    nums_map = {}
    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], i]
        nums_map[num] = i

 

기억해야할 기법

• enumerate
  
  • test = [1,2,3]
  • list(enumerate(test))
    # [(0, 1), (1, 2), (2, 3)]
• in dict()시 key를 기준
  • test = {'a':1,'b':2,'c':3}
  • for i in test:
    print(i,end='')
    # abc
• index가 필요한 경우, sort()를 사용하기 어려움
  • index가 섞이기 때문
• 중복 비교 연산을 피하는 법
  • 새로운 리스트를 만듦
  • 기존 리스트에서 하나씩 뽑아, 새로운 리스트의 내용과 순차 비교
  • 원하는 값을 못찾으면 새로운 리스트에 현재 값을 append

 

내가 구현한 코드

from itertools import combinations

def two_sum(nums: list[int], target: int) -> list[int]:
    for x, y in combinations(nums, 2):
        if x + y == target:
            one = nums.index(x)
            nums.pop(one)
            two = nums.index(y) + 1
            return [one, two]

• 책에서 나온 알고리즘에 비해 속도 차이가 매우 크다
• 내가 구현한 알고리즘 결과

• 책에서 구현된 알고리즘 결과

• 비교 연산의 중복을 피하기 위한 책의 구현 방식을 활용해야할듯