[Leetcode] 1. Two sum_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '1. Two sum'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Two sum' 알고리즘 문제

 

STEP 2. 'Two sum' 코드(code)

 

STEP 3. 'Two sum' 해설

 

STEP 4. 'Two sum' solution

 

반응형

 

STEP 1. 'Two sum' 알고리즘 문제

 

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.

 

지정된 정수 nums 배열과 정수 target, nums 배열에서 두 숫자의 인덱스를 반환하여 target에 합산합니다. 

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다. 

답변은 임의의 순서로 반환할 수 있습니다.

 

Constraints:

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

---

STEP 2. 'Two sum' 코드(code)

 

■ Runtime: 2792 ms, faster than 38.95% of Python online submissions for Two Sum.
■ Memory Usage: 14.3 MB, less than 69.95% of Python online submissions for Two Sum.

 

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i, a in enumerate(nums):
            check = target - nums[i]
            for j, b in enumerate(nums[i+1:]):
                if b == check:
                    return [i, i+j+1]
                else:
                    pass

---

STEP 3. 'Two sum' 해설

 

문제는 2개의 숫자를 더해서 target을 구하는 것입니다. 

이때, 처음 코드는 반복문을 통해 순차적으로 nums 배열에서 검사할 대상 check (target - nums [0])를 지정해서,

이중 반복문을 진행해 2번째 값을 찾는 방향으로 구했습니다.

 

이중 반복문을 통해 연산이 진행되서, 연산 속도가 상당히 느렸습니다. 이를 개선하기 위해 leetcode solution 코드를 살펴봤으며, dictionary를 활용해 계산했습니다.

 

 

STEP 4. 'Two sum' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 58 ms, faster than 78.56% of Python online submissions for Two Sum.
■ Memory Usage: 14.6 MB, less than 10.11% of Python online submissions for Two Sum.

 

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        seen = {}
        for i, value in enumerate(nums): #1
            remaining = target - nums[i] #2
            
            if remaining in seen: #3
                return [seen[remaining], i]  #4
            else:
                seen[value] = i  #5

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 'Two Sum'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.