이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
문제 정의
- 덧셈으로 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴
책에서 구현된 코드
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]
- 책에서 나온 알고리즘에 비해 속도 차이가 매우 크다
- 내가 구현한 알고리즘 결과
- 책에서 구현된 알고리즘 결과
- 비교 연산의 중복을 피하기 위한 책의 구현 방식을 활용해야할듯
'책읽기' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰][배열] 세 수의 합 (중요) (0) | 2021.07.19 |
---|---|
[파이썬 알고리즘 인터뷰][배열] 빗물 트래핑 (중요) (0) | 2021.07.19 |
[파이썬 알고리즘 인터뷰] 7장 - 배열 (0) | 2021.07.18 |
[파이썬 알고리즘 인터뷰][문자열] 가장 긴 팰린드롬 부분 문자열 (0) | 2021.07.18 |
[데이터 분석을 위한 SQL 레시피][2장] 이 책에서 다루는 도구와 데이터 (0) | 2021.07.18 |