[배열] 07 두 수의 합(Two Sum) ✔

<LeetCode 문제>

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

Two Sum - LeetCode

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴해야 합니다.

<풀이>

단순히 브루트 포스로 모든 경우를 살펴보면 다음과 같습니다.

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]

 

브루트 포스로 풀이할 경우 시간 복잡도가 O(N²)이므로 비효율적입니다.

모든 조합을 비교하지 않고 target에서 첫번째 값을 뺀 target-n이 존재하는지 in연산자를 통해 탐색하면 다음과 같습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,n in enumerate(nums):
            if target - n in nums[i+1:]: #nums에서 인덱스 i 이후에 target-n 있는지 살피기
                return [nums.index(n), nums[i+1:].index(target-n) + (i+1)] #해당 index반환

 

이 경우에도 in의 시간복잡도가 O(N)이고, list.index()의 시간복잡도도 O(N)이므로 전체 시간복잡도는 O(N²)입니다.

하지만 같은 시간복잡도여도 in 연산 쪽이 훨씬 더 가볍고 빠릅니다. 파이썬의 내부 함수로 구현된 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행되기 때문입니다.

 

해시 테이블로 구현된 딕셔너리를 통해 조회를 O(1)로 해서 전체 시간복잡도를 O(N)으로 만들면 다음과 같습니다.

(조회에서 최악의 경우 O(N)이지만 분할 상환 분석에 따른 시간복잡도는 O(1))

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        new_dict = {}
        for i,num in enumerate(nums):
            new_dict[num] = i #그 값에 대한 index를 value로 저장(여러개면 맨뒤에 있는걸로 저장)
        
        #[3,3], target=6일때 new_dict={3:1}
        #[3,2,4], target=6일때 new_dict={3:0,2:1,4:2}
        for i,k in enumerate(new_dict): #i는 nums에서 맨 처음 등장한 k의 index
            if target-k in new_dict:
                if i!=new_dict[target-k]: #같은 인덱스끼리 못 더하므로
                    return [i,new_dict[target-k]]

 

이때, nums에 같은수가 여러개 등장할 수 있다는 점도 생각해야 합니다. 처음에 잘못 풀이한 풀이는 다음과 같습니다

[잘못된 풀이]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        new_dict = {}
        for i,num in enumerate(nums):
            new_dict[num] = i #그 값에 대한 index를 value로 저장(여러개면 맨뒤에 있는걸로 저장)
            
        for i,k in enumerate(new_dict): #i는 nums에서 맨 처음 등장한 k의 index
            if target-k in new_dict:
                return [i,new_dict[target-k]]

 

이때 target-k가 k와 같으면 같은 index가 반환이 되어서 틀린 풀이가 됩니다.

 

딕셔너리의 조회 구조를 개선하면 다음과 같습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map={}
        #하나의 for문으로 통합
        for i,num in enumerate(nums):
            if target- num in nums_map: #무조건 다른 index니까 index같은경우 제외할필요X
                return [nums_map[target-num], i]
            nums_map[num] = i

<학습내용>

1. 딕셔너리는 해시테이블 기반이므로 조회가 O(1)인 점을 통해 시간복잡도를 줄일 수 있다.

<학습이 필요한 내용>

1. X

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/07_array/LC_1.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++