two-sum [leetcode 1]

https://leetcode.com/problems/two-sum

 

리트코드 첫번째 문제이다.

첫번째 문제답게 난이도는 낮은편이고 그럼 문제를 살펴보도록 하자.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]
 

Constraints:

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

 

입력으로 nums 리스트가 주어지고, 리스트 안에 숫자가 있는데 이 조합을 통해 target을 만드는 문제다.

제약조건을 살펴봐야하는데 리스트의 크기는 2 ~ 104 사이의 크기를 가지고 있고 오직 답은 1개만 나온다고 한다.

그래서 결국 최종적으로 리턴해야할 값은 리스트형태의 nums의 인덱스 위치다.

 

 

문제를 딱 보면 완전탐색(브루트포스) 형태로 모든것을 검색하면서 탐색할 수 있을거라 생각이 나서 바로 풀어봤다.

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]

 

0 1 2 3 이라는 인덱스가 있을때

0 1 -> 0 2 -> 0 3

1 2 -> 1 3

2 3

순서로 리스트를 순회하면서 확인하는 코드이다.

사실 보면 시간복잡도가 O^2이므로 속도면에서는 빠르지 않다.. 정확하게는 (0.5n^2) 정도가 되겠지만;

 

 

Dict 형태를 활용한다면 O(n)으로 시간복잡도를 줄일 수 있다.

실제로 실행해보면 가장 빠르게 동작할 수 있는 것을 확인해볼 수 있다.

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_dict:
                return [num_dict[complement], i]
            num_dict[num] = i
        return []  # 해답이 없는 경우 (문제 조건에 따르면 이 경우는 발생하지 않습니다)

 

간단하게 코드를 리뷰해보면

1. num_dict 빈 딕셔너를 생성하고

2. enumerate를 통해 num 인덱스 i를 가져오게 된다.

3. 현재 숫자 num와 합쳐 target이 될 수 있는 값을 complement로 계산한다.

4. complement 값이 num_dict 딕셔너리 안에 있는지 확인하고, 있다면 어떤 숫자와 현재 숫자가 합쳐져서 target이 될 수 있는 것을 의미한다.

5. 결국 complement가 num_dict에 있다면 complement 숫자의 인덱스와 현재 숫자의 인덱스를 반환하며 이게 return 된다.

 

 

 

 

 

ref

파이썬 알고리즘 인터뷰 (책)