[Leetcode] two sum을 4가지 방법으로 풀어보기 (python)

two sum은 많은 사람들이 리트코드를 입문하며 처음 푸는 문제같다.

알고리즘 책에서 이 문제를 다양한 방식으로 풀어보는데, 이 중 내가 알고있으면 좋을 풀이 (==나누면 좋을 지식)을 정리하려 한다.

투포인터 사용에 대한 이야기가 나오는데, 이 문제는 인덱스 값을 리턴하기에 투포인터 자체를 사용하여 풀 수는 없다. 

(투포인터 관련 문제는 이 포스팅 바로 다음에 이어질 예정이라 만약 투포인터를 사용한 알고리즘 풀이가 궁금하다면 다음 포스팅을 참고해주세요👍)

 

그래서 

 

1) Brute force로 풀이

2) in 을 사용한 풀이

3) 시간 복잡도를 개선해 속도를 높인 딕셔너리 사용 풀이

4) 3의 코드를 좀 더 간결하게 정리한 풀이

 

네가지를 공유할까 한다.

문제는 다음과 같다.

 

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.

 

출처: 

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]

 

제한사항

Constraints:

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

오직 하나의 유효한 정답이 있다고 가정한다.

 

related topic: array , hash table

 

 

 

[풀이1]

이중 for 문으로 배열을 순회한다. 순회 중 두수의 합이 target 과 같다면 해당 값들의 인덱스를 반환한다.

브루트 포스로 풀었을 때 코드는 다음과 같다. 직관적이지만 효율적이지 않다. 모든 원소를 순회하고 시간 복잡도는 이중 for문 사용으로 느리다. 풀 순 있지만 지나치게 느리기 때문에 지양하는 방식이다.

 

빅오표기법 참고

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]

 

 

 

[풀이2] in을 사용한 풀이

모든 조합을 비교하지 않고 타겟에서 첫번째 값을 뺀 target - n이 존재하는지 탐색하는 문제라고 생각해보자.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            complement = target - n
            
            if complement in nums[i + 1:]:
                return [nums.index(n), nums[i+1:].index(complement) + (i+1)]

파이썬의 내장함수 enumerate() 를 사용한다. 인덱스와 원소를 동시에 접근할 수 있게 하는데, 위의 코드처럼 i,n으로 언패킹(unpacking) 해주면 각 값을 다른 변수에 할당할 수 있다. (언패킹하지 않으면 튜플로 반환된다) 

complement는 보어, enumerate는 낱낱이 세다. 프로그래밍언어가 영어로 되어있어서 재밌을 때가 이런 때 같다.

해석하는 대로 무슨 말인지 와닿을 때!

첫 for문은 인덱스와 원소를 리턴한다. complement 변수가 nums array에 있는지를 [i+1:]로 범위를 한정하여 순회한다. 참고로 파이썬에서 

b = a[:2]
c = a[2:]

가 있다면, b는 처음부터 2번째 원소까지 / c는 3번째 요소부터 끝까지를 나타낸다. 따라서 위의 범위는 nums의 두번째 값부터 끝까지 순회하며 complemet를 찾는다. 

이 방식은 첫번째 브루트 포스보다 빠르다. 파이썬의 in 함수가 더 빠른 성능을 보이기 때문.

 

 

 

[풀이3] 

세번째 방법은 딕셔너리를 사용한 풀이이다. 딕셔너리는 해시 테이블로 구현되어 있기 때문에 조회는 평균 O(1)에 가능하다.(최악의 경우에는 O(n)이 될 수도 있다.) 딕셔너리는 리스트나 튜플처럼 순차적으로(sequential) 값을 구하지 않고 key를 통해 value 를 얻는다. 이것이 딕셔너리의 큰 특징인데, 예를들어 apple이라는 단어의 뜻을 찾기 위해 사전의 내용을 순차적으로 검색하는 것이 아니라 apple이 있는 곳만 펼쳐 보는 것이다. 기본 딕셔너리는 다음과 같은 형태로 구현된다. 

{Key1:Value1, Key2:Value2, Key3:Value3, ...}

Key와 Value의 쌍 여러 개가 { }로 둘러싸여 있다. 각각의 요소는 Key : Value 형태로 이루어져 있고 쉼표(,)로 구분되어 있다.

nums_map이라는 변수로 딕셔너리를 initialize한 뒤, 키와 밸류를 이용하여 문제를 풀이한다. 여기서 아이디어는, 

target에서 첫 번째 수를 빼면 두 번째 수를 바로 알 수 있다. 그렇다면 두 번째 수를 key로 하고 기존의 index를 value로 바꿔서 dictionary에 저장해두면, 나중에 두 번째 수를 key로 조회해서 정답(인덱스)을 즉시 찾아낼 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # dictionary initialize
        nums_map = {}
        
        # key와 value를 바꿔서 dictionary로 저장
        for i, num in enumerate(nums):
            # 원소가 key값이 된다 
            nums_map[num] = i
        
        # target에서 첫 번째 수를 뺀 결과를 key로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return [i, nums_map[target - num]]
            
            
        nums_map = {}

처음 보자마자 이 풀이를 생각해낼 수 있을 정도로 공부해야겠다

파이썬 딕셔너리에 대한 이해가 잘 되어있다면 빠르게 떠올릴 수 있는 아이디어였을지도..? 두고두고 다시 보고싶은 풀이! 

 

 

[풀이4] 

딕셔너리 저장과 조회를 두개의 for문으로 처리했던 방식을 개선하여, 하나의 for문으로 합쳐서 처리한다. 이 경우 전체를 모두 저장하지 않고 정답을 찾게되면 바로 함수를 빠져나오게 된다. 두번째 값을 찾기위해 매번 비교해야하기 때문에 풀이3에 비해 큰 성능상의 이점은 없으나 코드가 한결 간단해진다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i

 

 

 

이렇게 4가지 풀이방법을 살펴봤는데, 어렵고 난이도 높은 문제를 푸는 것보다 기본기가 탄탄한 사람이 되어야겠다고.. 간단한 문제를 풀면서 다시 한 번 느낀다ㅎㅎ 하나를 생각하더라도 성능을 고려하기 / 내가 쓰는 언어의 장점을 생각해보기 / 더 나은 방법이 있는지 생각해보기!

 

 

 

이 포스팅 내용은 파이썬 알고리즘 인터뷰 책을 참고했습니다:)