“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/two-sum/
내용이 정수로 구성된 배열 안의 특정 두 수의 합이 target과 같다면 해당 요소의 인덱스를 반환하는 문제다.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
리트코드의 1번 문제인만큼 쉬운 난이도지만 실행 시간을 빠르게 하려면 생각을 조금 해야한다. 당장 떠오르는 방법으로 무차별 대입 방식(브루트 포스)밖에 없어서 (#1) 올려 봤더니 실행 시간이 4초나 되는 엄청난 결과가 나왔다.
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 1
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]언어 처음 배울 때는 이런 반복문 쓰는 것도 버거웠었다. for를 중첩으로 쓰는 건 실무에서 흔하지만 학부에서 알고리즘 배울 때는 죄책감 느껴지는 문법이다. 책의 풀이 2번은 in을 사용해서 속도를 향상 시키고 있다. 리트코드에서 실행해보니 600ms로 #1보다는 빨라졌다.
# 2
for i, num in enumerate(nums):
complement = target - num
if complement in nums[i+1:]:
return [nums.index(num), nums[i+1:].index(complement) + (i+1)]맵(map)이 복잡도가 O(1)이라는 걸 배우고 나서는 배열과 해시맵을 활용해서 속도를 올리는 방법을 자주 썼던 기억이 난다. 그 이후로도 대개 맵을 잘 쓰는 것만으로 타임아웃이 발생하는 일은 없었지만 내부 구조 같은 건 신경 안 쓰고 있었지. #3은 딕셔너리를 활용한다. 이번에는 실행 속도가 60ms까지 내려간다.
# 3
nums_map = {}
for i, num in enumerate(nums):
nums_map[num] = i
for i, num in enumerate(nums):
if target - num in nums_map and i != nums_map[target-num]:
return [nums.index(num), nums_map[target-num]]#4는 3의 변형이므로 결과는 같았다.
그리고 책에 따르면 Go로 같은 코드를 실행 시키면 10ms 이하의 속도가 나온다고… 역시 상황에 맞는 최적화된 언어가 있기 마련이다. 처음 배운 언어가 C인데 학교 그만두고 싶다는 생각을 매일 같이 했었지. 지금의 파이썬도 이렇게 버거운데 말이다. 난 어떻게 먹고 살아야 하는 걸까.