[LeetCode] 1.두 수의 합(Two Sum)

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

단, 정답은 하나이다.

 

1. 내가 직접 푼 코드

 

class Solution:
    def twoSum(nums: list, target: int) -> list:
        # 브루트 포스로 계산
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

 

해설 :

 

단순 반복으로 풀었다.

반복문 두개로 진행하다 보면 target 값을 구할 수 있다.

단, 시간이 너무 많이 든다.

 

RunTime : 4012ms

 

 

 

 

 

** 여러가지 답안 **

 

2. in을 이용한 탐색

 

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

 

해설:

 

모든 조합을 비교하지 않고 target - n이 존재하는지 탐색하는 문제로 변환.

위 코드와 같이 시간 복잡도는 O(n^2)으로 같지만,

같은 시간 복잡도라도 in 연산이 훨씬 가볍고 빠르다.

 

RunTime : 640ms

 

 

 

 

3. 첫 번째 수를 뺀 결과 키 조회

 

class Solution:
    def twoSum(self, nums: list, target: int) -> list:
            nums_map = {}
            # 키와 값을 바꿔서 딕셔너리로 저장
            for i, num in enumerate(nums):
                nums_map[num] = i
 
            # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
            for i, num in enumerate(nums):
                if target - num in nums_map and i != nums_map[target - num]:
                    return [i, nums_map[target - num]]

 

해설:

 

딕셔너리의 키에 숫자를, 값에 index를 넣는다.

그 후 위의 complement를 딕셔너리에서 찾고 두 인덱스가 다르면

찾고자 하는 값이므로 두 인덱스를 리턴한다.

위의 두 시간 복잡도는 O(n^2)인데 이 풀이는 O(n)이다.

 

RunTime : 56ms

 

 

 

4. 조회 구조 개선

 

class Solution:
    def twoSum(self, nums: list, target: int) -> list:
            nums_map = {}
            # 키와 값을 바꿔서 딕셔너리로 저장
            for i, num in enumerate(nums):
                if target - num in nums_map:
                    return [nums_map[target-num],i]
                nums_map[num] = i

 

해설:

 

3번 코드에서는 반복문을 두 번 불렀는데

여기서는 반복문을 한 번만 사용하여 코드를 간결하게 하였다.

실행 시간의 변화는 그다지 없다.

 

RunTime : 60ms

 

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]