[LeetCode 해석 및 풀이] 1. Two Sum

LeetCode 문제 해석 및 풀이 방법
 

문제 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.
 

한글

숫자로 된 배열이 주어지면, 두개를 더해서 target이 되는 index를 반환합니다.
 
각 입력에는 정확히 하나의 해답이 있다고 가정하며, 같은 요소를 두 번 쓸 순 없습니다.
 
답 순서는 아무렇게나 해도 됩니다
 

제한조건

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 유효한 답은 하나만 존재합니다.

 

입출력 예

입력	출력
nums = [2,7,11,15], target = 9	[0,1]
nums = [3,2,4], target = 6	[1,2]
nums = [3,3], target = 6	[0,1]

 

해답 및 해설

파이썬 (Python)

우선 해쉬 테이블을 쓰지 않고는 다음과 같은 방식으로 할 수 있을듯 하다

1. 반복문으로 리스트를 2번 돌아 맞는 한쌍을 찾음
2. 크기순으로 정렬 후 리스트의 원소를 순서대로 체크하며 한쌍 찾기 (1보단 나음) => Two sum 2번 문제 상황

하지만 위 두 방법은 시간복잡도가 O(n^2), O(nlogn)이므로 좋지는 못한 방법이다. neetcode 로드맵에 나온대로 해쉬를 이용하면 O(n)의 복잡도로 해결할 수 있다.
 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}
        for i, num in enumerate(nums):
            index_list = nums_dict.get(num, [])
            index_list.append(i)

            nums_dict[num] = index_list

        for x in nums_dict.keys():
            num1 = x
            num2 = target - x

            idx1_list = nums_dict.get(num1)
            idx2_list = nums_dict.get(num2)

            if not idx1_list or not idx2_list: continue

            if num1 == num2:
                if len(idx1_list) < 2: continue
                return [idx1_list[0], idx1_list[1]]
            
            return [idx1_list[0], idx2_list[0]]

 
우선 나오는 숫자들과 인덱스를 사전에 넣어준다. 숫자가 여러번 나올 수 있으므로 값에 리스트 형태로 넣어준다. 이후 각 key들의 경우에서 target을 만드는 나머지 숫자가 사전에 있는지 찾아본다.