알고리즘 - 두 수의 합
덧셈을 하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.Permalink
| Input | Output |
|---|---|
| [2,7,11,15], 9 | [0,1] |
| [3,2,4], 6 | [1,2] |
| [3,3], 6 | [0,1] |
Soultion1 (브루트 포스로 계산)Permalink
def twoSum(nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
가장 간단하게 풀 수 있지만 모든 요소를 모두 차례대로 비교 시간복잡도는 O(n²)
Solution2 (in을 이용한 탐색)Permalink
def twoSum(nums: List[int], target: int) -> List[int]:
for i in enumerate(nums):
complement = target - n
if complement in nums[i + 1:]:
return [nums.index(n), nums[i + 1:].index(complement) + (i + 1)]
시간복잡도는 solution1과 동일하지만 in 연산 쪽이 훨씬 가볍고 빠르다.
파이썬의 내부 함수로 구현된 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행된다.
Solution3 (첫 번째 수를 뺀 결과 키 조회)Permalink
def twoSum(nums: List[int], target: int) -> List[int]:
def twoSum(self, nums: List[int], target: int) -> List[int]:
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 [i, nums_map[target - num]]
i != nums_map[target - num] 을 검사해주는 이유는 자기 자신의 인덱스를 두 번 더한 값일 경우를 제외하기 위해서이다.
[3, 2, 4] , 6 일 경우 [2, 4]가 나와야 하지만 이 검사를 해주지 않으면 [3, 3]이 나온다.
Solution4 (조회 구조 개선)Permalink
def twoSum(nums: List[int], target: 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
딕셔너리 저장과 조회를 2개의 for문으로 처리 한 것을 하나의 for로 합쳤지만 두 번째 값을 찾기 위해 매번 비교해야 하기때문에 성능상의 큰 이점은 없다.
Solution5 (투 포인터 이용) -> 풀이 불가Permalink
인덱스 처음과 끝을 가리키고 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키고 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로 이동시킨다.
def twoSum(self, nums: List[int], target: int) -> List[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]
코드도 간결하고 보기 쉽다. 또한 시간 복잡도도 O(n)으로 불필요한 추가 계산도 없어 빠를 것으로 기대하지만 이 문제는 투 포인터로 풀 수 없다.
왜냐하면 입력이 정렬된 숫자가 아니고 sort를 통해 정렬한다고 하더라고 인덱스 위치가 꼬이기 때문이다.
인덱스 위치가 아니라 값을 찾아내는 문제라면 얼마든지 정렬하고 투 포인터로 풀이 할 수 있다.
댓글남기기