문제
Your input [2,7,11,15]
target: 9
Expected [0,1]
1. 브루트 포스로 계산
브루트포스: 모든 조합을 더해서 일일이 확인하는 무차별 대입 방식
class Solution:
def twoSum(self, 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]2+7, 2+11, 2+15와 같이 마지막 요소들까지 모두 차례대로 비교해 가며 타겟값이 나올때 까지 반복한다.
이 경우 풀이 시간 복잡도는 0(N제곱)이다. 정확히는 (1/2)N제곱정도 지만...
어쨋든 문제야 풀리기 하겠지만 너무 오래걸린다. 좀 더 최적화 된 방법이 필요하다.
2. in을 이용한 탐색
모든 조합을 비교하지 않고 경우의 수를 줄일 수 있는 방법은 없을까? 타겟 값에서 첫번째 뺀 값이 배열안에 존재하는지 탐색하는 문제로 변경해보자.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, n in enumerate(nums):
complement = target - n
if complement in nums[i + 1:]:
return [nums.index(n), nums[i+1:].index(complement) + (i + 1)]in의 시간 복잡도는 O(n)이고 전체 시간 복잡도는 이전과 동일한 0(N제곱)이다. 시간 복잡도는 같지만 in으로 연산하는 쪽이 훨씬 더 빠르고 가볍다.
3. 첫 번째 수를 뺀 결과 키 조회(딕셔너리 활용)
딕셔너리는 해시 테이블로 구현되어 있으며 조회는 평균적으로 O(1)에 가능하다.
class Solution:
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]]첫 번째 수를 빼면 두 번째 수를 바로 알수 있고 두 번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔 딕셔너리에 저장하는 방식이다.
그러면 두 번째 수를 키로 조회해서 정답을 바로 찾아 낼 수 있을 것이다.
4. 조회 구조 개선
3번의 딕셔너리의 저장,조회 2개의 for문을 각각 처리했던 방식을 개선해 하나의 for문으로 처리해 볼 수 있다. 전체를 모두 저장할 필요없이 정답을 찾았으면 바로 빠져나오는 방식이다.
하지만 어차피 매번 비교해야 하기 때문에 성능상의 큰 효과는 없을 것이다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_map = {}
#하나의 for 문으로 통합
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target - num], i]
nums_map[num] = i값을 다 저장하지 않고 바로 대입하여 조회해서 바로 빠져나온다.
5. 투 포인터 이용
투 포인터를 이용하는 방식은 간단하다. 가장 왼쪽과 가장 오른쪽의 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로 값이 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 찾는 방식이다.
타겟인 9를 찾기위해 2.7.11.15중 2와 15를 더하면 타겟보다 크니 오른쪽 포인터15를 11로 옮긴다. 아직도 타겟보다 크니 11포인터를 7로 옮기면 우리가 원하는 값을 찾을 수 있다.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums.sort()
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]
그러나 이 방식은 모든 값이 정렬되어 있을 때만 가능하다. 3.2.4순으로 정렬되어 있지 않다면 원하는 값을 찾지 못한다. 정렬을 하게 sort를 사용하더라도 값을 찾을 수는 있지만 인덱스의 값을 찾는 문제라면 인덱스 값이 정렬때문에 뒤죽박죽되어 원하는 결과를 얻을 수 없다.
번외6.고(Go) 구현
만일 동일한 알고리즘을 다른 언어로 작성해 보면 어떨까?
GO언어로 작성한 3. 첫 번째 수를 뺀 결과 키 조회(딕셔너리 활용)이다. 이 경우 파이썬 보다 훨씬 빠르게 16ms만에 실행됐다. 동일한 방법이지만 더 최적화된 언어로 작성하면 이처럼 다른 실행속도를 보여준다.
func twoSum(nums []int, target int) []int {
numsMap := make(map[int]int)
// 키와 값을 바꿔서 딕셔너리로 저장
for i, num := range nums {
numsMap[num] = i
}
// 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
for i, num := range nums {
if j, ok := numsMap[target-num]; ok && i != j {
return []int{i, j}
}
}
return []int{}
}
