[Leetcode 아주 상세한 문제풀이] 1. Two Sum – 코드 line 별 설명

Leetcode 문제

리트코드의 대표 문제 중 하나인 Two sum 은 쉽지만 다양한 접근 방식이 있는 문제다.

우선 문제를 살펴보자.

 

리트코드 1번 문제 Two Sum (링크)

Two Sum - LeetCode

Two Sum - LeetCode

 

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.

 

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]

 

 

문제 설명

문제에 대해 간략히 설명하자면 정수 리스트와 하나의 타겟 넘버가 인풋으로 주어진다.

이때 정수 주어진 리스트에서 숫자 2개를 골라 그 합이 타겟 넘버와 같은 숫자 조합을 찾는 문제다.

이때 그 2개의 숫자 대신 그 숫자의 index를 아웃풋으로 출력해야 한다.

위의 첫번째 예시에서 볼 수 있듯이 정수 리스트로 [2, 7, 11, 15]가 주어지고 타겟 넘버로 9가 주어졌다면, 오직 2와 7의 조합으로만 숫자 9를 만들 수 있다.

따라서 정수 리스트에서 2와 7의 index인 [0, 1]을 아웃풋으로 출력해야 한다.

문제에서 정의한대로 이 문제에는 단 하나의 솔루션이 존재하기 때문에 여러 조합으로 타겟 넘버를 만들어야 하는 고민을 할 필요가 없다.

 

 

문제 접근법

이 문제는 2가지 방식으로 접근할 수 있는데

첫번째 방법은 Every single combination을 구하는 것이고

두번째 방법은 Dictionary storage를 이용하는 방법이다.

첫번째 방법은 double loop를 사용해야 하기 때문에 O(n^2)

두번째 방법은 Store in dictionary (+enumerate)를 사용해야 하기 때문에 O (n)의 time complexity가 있다.

 

 

문제 풀이 #1

우선 정수 리스트와 타겟 넘버에 대한 함수를 정의한다 (line 1)

그리고 리스트 길이만큼 첫번째 for문을 돌리고,

두번째 for문을 탐색하고 있는 인덱스 'i' 바로 다음 인덱스 'i+1'부터 돌린다. (line 4)

그리고 첫번째 for에서 돌리는 숫자와 두번째 for에서 돌리는 숫자의 합이

타겟 넘버와 같은지 확인한다 (line 5)

만약 그 합이 타겟 넘버와 같다면 그 숫자들의 인덱스를 출력한다 (i.e., [i, j]) (line 6)

하지만 이 솔루션은 모든 정수의 조합을 검사해야 하기 때문에 time complexity가 크다.

따라서 좀 더 효율적인 방법으로는 dictionary를 사용하는 방법이 있다.

 

 

문제 풀이 #1 코드

def two_sum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # Return empty list if no solution is found
 
# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)

 

 

문제 풀이 #2

우선 정수 리스트와 타겟 넘버에 대함 함수를 설정한다. (line 1)

그 후 주어진 정수 리스트에 대해 숫자와 인덱스를 enumerate하여 for문을 돌린다. (line 4)

이때 타겟 넘버에서 for문에서 돌리고 있는 숫자를 빼는데 (line 5)

결국 이 숫자가 주어진 정수 리스트에 있다면 for문에서 돌리고 있는 숫자와 합이 타겟 넘버가 되기 때문에

if문을 사용하여 그 숫자가 정수 리스트에 있는지 찾는 구문이 필요하다 (line 6)

만약 그 숫자가 있다면 그 숫자와 for문에서 돌리고 있는 숫자의 인덱스를 출력한다.

 

 

문제 풀이 #2 코드

def two_sum(nums, target):
    num_indices = {}
 
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_indices:
            return [num_indices[complement], i]
        num_indices[num] = i
 
    return []  # Return empty list if no solution is found
 
# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)

 

1. Two Sum