(LeetCode)1. 두 수의 합

문제

Two Sum - LeetCode

아이디어

  • 브루트 포스로 계산하면 쉽게 계산할수 있으나 시간복잡도가 O(N^2)으로 굉장히 느림
  • 첫 번째 수를 뺀 결과 키조회 → 비교나 탐색 대신 한번에 정답을 찾는 방법

코드

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 nums.index(num), nums_map[target - num]

배운점

  • 딕셔너리는 해시테이블로 구성되어있고, 이 경우 조회는 평균적으로 O(1)에 가능(최악의 경우 O(n))