두 수의 합

첫 번째 제출

브루트포스

from itertools import combinations
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]

Runtime
3843 ms
Memory
14.9 MB

처음에는 collections로 풀고 index로 위치 구하려다 안돼서 브루트포스로 풀었다. 매우 느리다.

두 번째 제출

in을 이용한 탐색

from itertools import combinations
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num in enumerate(nums):
            pair = target - num
            if pair in nums[i+1:]:
                print(num, pair)
                return [i, nums[i+1:].index(pair)+i+1]
                # return [i, nums.index(pair)] 똑같은 원소면 오류

Runtime
665 ms
Memory
14.8 MB

세 번째 제출

딕셔너리를 이용한 키 조회

from itertools import combinations
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, num in enumerate(nums):
            num_dict[num] = i

        print(num_dict)
        for i, num in enumerate(nums):
            comp = target-num
            if comp in num_dict and i != num_dict[comp]:
                return [i, num_dict[comp]]

하나하나 다 돌아볼 필요없이 딕셔너리로 키 조회하면 훨씬 빠르게 탐색이 가능하다.

+)

• 두 숫자의 합이면 타겟에서 뺀 것을 찾으면 된다.
• 딕셔너리 키 조회가 리스트 하나씩 돌아보는 것보다 훨씬 빠르다.
  in의 시간복잡도 : O(n)
  키 조회 시간복잡도 : O(1)