Leetcode 1. Two Sum with Python - 리뷰 O

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

양의 정수 배열 nums와 정수 target이 주어집니다,
더했을때 target이 되는 배열의 두 숫자의 인덱스를 배열로 만들어 리턴하세요.

예시

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

2와 7을 더하면 target인 9가 된다, 그렇기에 2와 9의 인덱스인 0과 1을 배열로 감싸 리턴했다.

제한

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• 정답은 항상 단 1개 존재함.

풀이법

1. BRUTE FORCE

모든 숫자쌍의 경우를 전부 확인하는 것.

시간 복잡도는 O(n^2) 이고 공간복잡도는 O(1) 이다.

  def twoSum(numbers, target):
      for i in range(len(numbers)):
          for j in range(i+1, len(numbers)):
              if numbers[i] + numbers[j] == target:
                  return [i, j]
                 

2. MAP

우리가 알아야 하는것은 두 숫자를 더했을때 특정 숫자가 되도록 하는것을 찾는것이다.

두 숫자가 A와 B이고 찾아야 하는 숫자가 T일때 A + B = T 가 성립시 B = T - A도 성립한다.

즉 A에 맞는 B라는 숫자는 T - A라는 값이 되어야 한다는 것이다.

이를 위 문제에 적용시, 첫번째 2라는 숫자에 target이 9이기 때문에 뒤에 나오는 숫자들 중 9가 있냐 없냐를 확인할수 있다면 될것이다.

이를 위해 MAP, 파이썬의 dictionary를 이용해 필요한 숫자들을 미리 적어둬 O(1)의 시간복잡도로 해결할수 있다.

이를 위한 코드는 다음과 같다.

 def twoSum(numbers, target):
    d = dict()
    for i in range(len(numbers)):
    	# 자기 자신이 앞에 있었던 숫자들중 필요한 숫자였을 경우, 리턴.
        if numbers[i] in d:
            return [d[numbers[i]], i]
        # 그렇지 않다면 dictionary에 자기 자신과 더해졌을때 target이 되는 숫자를 찾기위해 등록.
        else:
            d[target - numbers[i]] = i
            

시간복잡도는 O(n)이 되며, 공간복잡도는 dict를 사용하기에 O(n)이 된다.

(2024/11/19 추가)

3. Two pointer

• 오랜만에 초심으로 돌아오고자 한개 더 남겨본다.
• index 정보를 남겨야 하기 떄문에 nums를 약간 수정해야 한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        nums = [(num, i) for i, num in enumerate(nums)]

        nums.sort(key=lambda k: k[0])

        N = len(nums)

        left = 0
        right = N - 1

        while left < right:
            if nums[left][0] + nums[right][0] < target:
                left += 1
            elif nums[left][0] + nums[right][0] > target:
                right -= 1
            else:
                return [nums[left][1], nums[right][1]]