알고리즘 | array - twoSum

input

nums = [2,7,11,15]

output

[0,1]

풀이1: 브루트 포스로 계산

모든 요소를 차례대로 비교해서 구 하는 방법이 있다.
즉, 2+7, 2+11, 2+15와 같은 식으로 마지막 요소들까지 모두 차례대로 비교해 가며 정답을 찾을 떄까지 계속 진행한다.
이 방식이 무차별 대입 방식인 브루트 포스로서, 앞으로 문제를 풀때 비효율적인 방법임을 숙지해야한다.

시간 복잡도 : $O(n^2)$, 정확히는 $\frac{1}{2}n^2$
소요 시간 : 5,284ms

아는분은 아시겠지만 시간복잡도 표기시 상수항은 기입하지 않으므로 $n^2$

결론: 너무 느림

from typing import List

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]

nums = [2,7,11,15]
target = 26
print(twoSum(nums, target))

풀이2: in을 이용한 탐색

모든 조합을 비교하지 않고 타겟에서 첫 번째 값을 뺀 값 target -n이 존재하는지 탐색 하는 문제로 변경해볼게요.

여기서의 in의 시간 복잡도는 $O(n)$이며, 따라서 전체 시간 복잡도는 이전과 동일한 $O(n^2)$이다. 그런데 여기서는 같은 시간 복잡도라도 in 연산쪽이 훨씬 빠르다.

시간복잡도 : $O(n)$

시간복잡도 : 800~900 밀리초

from typing import List

def twoSum(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)

nums = [2,7,11,15]
target = 26
print(twoSum(nums, target))

풀이3: 첫 번째 수를 뺀 결과 키 조회

비교와 탐색 대신 한 번에 정답을 찾는 방법은?

먼저 타겟에서 첫 번쨰 수를 빼면 두 번째 수를 바로 알아낼 수 있습니다. 그렇다면 두 번째 수를 키로 하고 기존의 인덱스는 값으로 바꿔서 딕셔너리로 저장해두면, 나중에 두 번째 수를 키로 조회해서 정답을 즉시 찾아 낼수 있을거에요.

step 1, 키와 값을 바꿔서 딕셔너리로 저장
step 2, 그럼 키가 2,7,11,15가 되고 value는 0,1,2,3,4가 되요.
step 3, 두 번째로 enumerate 기존에 정의한 nums 리스트로 돌려볼게요.

• 이 때 중요한 것이 if문으로 분기하게 될 경우 반드시 target - num in nums_map를 처음에 놓아야해요.

  • 만약 i != nums_map[target - num]이 순서가 바껴 앞에 오게 될 경우 KeyError가 발생하여 루프가 돌아가지 못해요.
    • target에서 nums리스트의 요소 첫 번째 값을 빼고(예.26-2) 나온 결과가 딕셔너리의 키값으로 있는지 확인합니다. 만약 없다면 뒤의 조건은 확인 하지도 않고 loop로 돌아가서 다음 인덱스 턴으로 넘겨서 if문을 이전과 같이 조건을 확인하면서 맞는지 안맞는지 비교하는 거조.

시간복잡도 : $O(1)$

시간복잡도 : 48 밀리초

def twoSum(nums:List[int], target: int) -> List[int]:
    # 키와 값을 바꿔서 딕셔너리로 저장
    nums_map = {val:idx for idx, val in enumerate(nums)}

    # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums): 
        if target - num in nums_map  and  i != nums_map[target - num]:
            return nums.index(num), num_map[target - num]
        
nums = [2,7,11,15]
target = 26 # 리스트에서 두 개의 요소를 더한 값
print(twoSum(nums, target))

풀이4: 조회 구조 개선

딕셔너리 저장과 조회를 2개의 for문으로 처리했던 방식을 더 개선하여 이번에는 하나의 for로 합쳐서 처리해볼게요.
이 경우 변수에 저장할 필요 없이 정답을 찾아서 함수를 빠져나오게 되요. 그러나 두 번쨰 값을 찾기 위해 매번 비교해야하기 때문에 앞서 풀이에 비해 성능상의 이점은 없어요.

하지만 코드 수가 줄어 들어 한 눈에 파악하기는 더 쉽다고 느낍니다.

from typing import List

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
        
nums = [2,7,11,15]
target = 26 # 리스트에서 두 개의 요소를 더한 값
print(twoSum(nums, target))