[LeetCode] 1. Two Sum - Python

MinWoo Park·2021년 5월 7일

Algorithm

목록 보기

32/42

Algorithm Problem with Python — 32day

문제 설명 📖

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

제한사항

2 <= nums.length <= 103
109 <= nums[i] <= 109
109 <= target <= 109
Only one valid answer exists.

입출력 예

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

문제 이해 🔑

리스트와 타겟이 주어지면 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하는 문제입니다.
문제 자체는 매우 쉬우나 최적화할 수 여러 가지 방법이 있으니 어떤 방식으로 최적화를 할 수 있는지 체크하는 문제입니다.

수도 코드 ✍️

타겟에서 첫 번째 수를 빼면 두 번째 수를 바로 알 수 있기에 이러한 방식으로 접근합니다.

enumerate를 통해 index, value를 얻은 후 키와 값을 바꾸어 딕셔너리로 저장합니다.
타겟에서 첫 번째 수를 뺀 결과로 키를 조회합니다.
타겟에서 첫 번째 수를 뺸 값(편의상 a로 지칭)이 딕셔너리에 존재하고, 첫 번째 수의 인덱스가 딕셔너리 키a의 값이 아니라면 첫 번째 값의 인덱스와 딕셔너리의 키 a의 값을 리턴합니다.

코드 작성 ⌨️

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]]

정리 😄

문제 자체는 정말 쉬웠습니다.
이 문제의 최적화를 공부하기 이전에는 Brute-Force로 계산했었습니다.
이중 for문을 이용하여 모든 조합을 일일이 확인해 O(n²)의 시간복잡도를 가졌을 겁니다.
이 문제의 경우 타겟에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다는 점을 활용하여 두 번째 수를 키로 하고 기존의 인덱스를 값으로 바꿔서 딕셔너리로 만드는 방식을 사용하여 O(n)의 시간복잡도로 줄일 수 있었습니다.
LeetCode에서는 52ms만에 실행된 것을 확인할 수 있었습니다.