배열 : 두 수의 합(리트코드 1번)

▶ 문제 : https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

##### 문제 #####
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

##### 입력 #####
nums = [2, 7, 11, 15]
target = 9

##### 출력 #####
[0, 1]

 

▶ 접근 방법

여러 가지 접근 방법을 생각해볼 수 있었다.
우선, 브루트 포스 방식의 완전탐색을 수행하여 전체 가능한 경우를 모두 살펴볼 수 있었으나
시간 복잡도를 고려할 때, 좋은 방법은 아니었다.

이후, target에서 nums의 숫자를 뺀 결과를 딕셔너리에서 조회하는 방식으로 문제를 해결하였다.

 

▶ 풀이 코드

from typing import List

nums = [2, 7, 11, 15]
target = 9

def two_sum(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]

print(two_sum(nums, target))


###################################################
def two_sum(nums: List[int], target: int) -> List[int]:
    temp = {}
    for index, num in enumerate(nums):
        temp[num] = index
    print(temp)
    for index, num in enumerate(nums):
        if target - num in temp and index != temp[target - num]:
            return [index, temp[target - num]]

print(two_sum(nums, target))

###################################################
def two_sum(nums: List[int], target: int) -> List[int]:
    temp = {}
    for index, num in enumerate(nums):
        if target - num in temp :
            return [temp[target - num], index]
        temp[num] = index

print(two_sum(nums, target))

 

▶ 관련 링크