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.

 

 

[제약 사항]

- $2 <= nums.length <= 10^3$

- $-10^9 <= nums[i] <= 10^9$

- $-10^9 <= target <= 10^9$

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

 

출처: [LeetCode]

 

문제에 대한 나의 접근

 

우선 문제에 대한 내용은 배열과 target 값을 입력받고, 배열 내 요소 중 2개 요소를 더해 target값과 같을 때 배열 내 해당 요소의 index를 반환하면 된다.

 

# 첫 번째로는 단순히 모든 경우의 수를 이용해 답을 찾는 방법인 Brute Force를 진행했다.

 

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
                else:
                    pass

 

이중 for문을 이용해서 진행을 했는데 첫 번째 요소가 선택되고 그 다음 요소들을 순차적으로 더하다가 9가 되면 그 순간에 더해진 요소의 인덱스를 반환한다. 이 코드로 실행했더니 아래와 같은 결과를 보였다.

 

 

# 두 번째로는 Dictionary를 이용해서 진행했다.

 

class Solution:
    def twoSum(self, nums, target):
        dic = {}
        for idx, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], idx]
            else:
                dic[num] = idx

 

입력받은 배열을 열거(enumerate)해서 반복되는 동안 인덱스와 요소를 딕셔너리에 입력하다가 target에서 요소를 뺀 값이 딕셔너리에 있을 때 해당 요소의 인덱스와 딕셔너리 내 target에서 요소를 뺀 값에 해당하는 인덱스를 반환. 이 코드로 실행했더니 아래와 같은 결과를 보였다.

 

 

두 개의 코드 모두 정상적으로 실행은 되었지만 코드의 성능부분에 있어서는 다른 결과를 보였다. 조금 더 나은 방법을 연구해보고 다시 테스트를 해볼 예정이다.