[알고리즘][배열] - 2. 두 수의 합

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

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

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

---

[브루트 포스 풀이(Brute force)]

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]

• 차례대로 다른 요소들을 모두 비교하면서 답을 돌려준다. 
• 즉 정답을 찾을 때까지 모두 비교하며 계속 진행한다. 이 방식이 바로 무차별 대입인 브루트 포스로서, 대부분 이 방법은 굉장히 비효율적이다. 

 

 

[in 을 이용한 탐색]

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)]

• 모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지를 탐색하여 있다면 그 값의 index를 돌려주는 방식을 보여주고 있다. 
• 이때 list에 있는 값들을 enumerate로 바꿔서 사용한다.
  • 그이유는 enumerate가 인덱스 번호와 컬렉션의 원소를 tuple형태로 반환해주기 때문이다.
• complement = target - n
  • complemet는 첫 번째 값을 의미한다. 
  • 이 값을 제외하고 나머지를 돌면서 target과 같은 값이 있는지를 확인해준다.
• if complement in nums[i+1:]:
  • 첫 번째 값을 제외하고 마지막 index까지 돌아야 하기 때문에 nums[i+1:]로 지정한 것이다.
• return [nums.index(n), nums[i+1:].index(complement)+(i+1)]
  • 첫 번째 값의 index를 돌려주고 그 값을 뺀 나머지가 nums에 존재한다면 그 값의 index를 돌려준다는 뜻이다. 

 

 

[첫 번째 수를 뺀 결과 키 조회]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        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]]

• for i, num in enumerate(nums):
  • 키 = index, 값 = nums의 요소들
• nums_map[num] = i
  • index 값을 사용하기 위해서 nums_map 딕셔너리에 nums 값을 key로 넣어주고 nums의 인덱스를 value로 넣어준다. 
• if target - num in nums_map and i != nums_map[target-num]:
  • target에서 nums[num]을 뺀 값이 저장해놓은 딕셔너리에 있고 그 값이 본인이 아니라면
• return [i, nums_map[target - num]
  • 그 값을 돌려준다. 

 

 

[위의 코드를 더 간결하게 쓴 코드]

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:
                return [nums_map[target-num], i]
            nums_map[num] = i

• 위의 코드와 시간 복잡도 차이가 그다지 많이 안 나지만 코드가 간결 해졌다. 

 

 

[투 포인터를 이용할 수 있을까?]

투 포인터를 사용하기 위해서는 list의 값을 정렬 해주어야 할텐데 그렇게 되면 index를 돌려주어야 하는 이 문제의 취지에서 벗어나기 때문에 이 경우 투 포인터를 사용해서 문제를 풀 수 없게 된다.

 

 

[같은 시간 복잡도를 가졌지만 실행속도가 다른 이유는?]

• 일반적으로 시간 복잡도를 표기할 땐 상수항을 적지 않는다.
• 그렇기 때문에 같은 시간 복잡도에서도 실행 속도는 서로 다를 수 있다. 

 

 

[실행 속도 비교]

• 위의 코드 순서대로 제출했다.