선형 자료구조_1. Two Sum

leetcode 1. Two Sum

문제

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

입출력예시

• 입력:

nums = [2, 7, 11, 15], target = 9

• 출력:

[0, 1]

풀이

다양한 방법으로 풀 수 있는 문제로 브루트 포스(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]

• runtime: 4032 ms
• memory: 14.8 MB

자바스크립트

const twoSum = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  } 
}

• runtime: 132 ms
• memory: 39.1 MB

브루트 포스(Brute-Force)는 모든 조합을 일일이 확인하는 무차별 대입 방식으로 다음과 같이 작동한다.

nums = [2, 7, 11, 15], target = 26

2 + 7 = 9 
2 + 11 = 13
2 + 15 = 17
7 + 11 = 18
7 + 15 = 22
11 + 15 = 26 // target

그러나 파이썬의 경우 런타임이 지나치게 오래걸린다. 이는 시간 복잡도가 O(n²)이기 때문으로, 다른 방식을 통한 최적화가 필요한 것을 확인할 수 있다.

딕셔너리(객체) 이용

파이썬

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

• runtime: 120 ms
• memory: 15.4 MB

자바스크립트

const twoSum = function(nums, target) {  
  let numsMap = {};
  // 키와 값을 바꿔서 객체로 저장
  for (let i = 0; i < nums.length; i++) {
    numsMap[nums[i]] = i;
  }

  // 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
  for (let i = 0; i < nums.length; i++) {
    if(numsMap[target - nums[i]]  && i !== numsMap[target - nums[i]]) {
      return [i, numsMap[target - nums[i]]];
    }
  }
}

• runtime: 120 ms
• memory: 41.3 MB

다음과 같이 target에서 첫 번째 값을 뺀 값이 존재하는지 여부를 탐색하면 모든 조합을 비교할 필요가 없어진다.

nums = [2, 7, 11, 15], target = 26

numsMap = {
  "2": 0, 
  "7": 1,
  "11": 2, 
  "15": 3
}

26 - 2 = 24
26 - 7 = 19
26 - 11 = 15 // target

[2, 3]

딕셔너리(객체)를 이용해 키를 조회하는 것이 핵심으로, 두 번째 수의 인덱스를 바로 조회할 수 있어 평균적으로 O(1)의 시간 복잡도를 가진다. 덕분에 파이썬의 경우 런타임이 확연하게 짧아진 것을 확인할 수 있다.

참고
파이썬 알고리즘 인터뷰