Two Sum

문제 링크

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

문제 설명

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

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

출력
[0, 1]

설명
nums[0] + nums[1] = 2 + 7 = 9

풀이 전략

• 풀이 전략은 아래와 같이 다양하게 접근 할 수 있다.
  1. Brute-Force 계산
  2. in을 이용한 탐색
  3. 첫 번재 수를 뺀 결과 키 조회
  4. 조회 구조 개선
  5. 투 포인트 이용
• 5가지 중 가장 추천하는 풀이 전략은 4번 이며, 5번은 문제 풀이를 못할 수도 있다.

조회 구조 개선

• for 문 하나로 해결
• 전체를 모두 저장할 필요 없이 정답을 찾게 되면 함수를 빠져 나올 수 있다
• 코드가 한결 더 간결해 진다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}                        # 1. 숫자와 인덱스를 저장할 딕셔너리 생성
        for i, num in enumerate(nums):       # 2. 배열을 순회하면서 조건을 확인
            if target - num in nums_map:     # 3. (target - num) 값이 이미 nums_map에 있는지 확인
                return [nums_map[target - num], i]  # 4. 있다면 그 인덱스와 현재 인덱스 반환
            nums_map[num] = i                # 5. 없다면 현재 숫자와 인덱스를 딕셔너리에 추가

코드 분석

1. 딕셔너리 생성
   :nums_map은 각 숫자와 그 숫자의 인덱스를 저장하는 딕셔너리입니다.
   이를 통해 상수를 이용해 값을 찾을 수 있는 빠른 조회가 가능합니다.
   nums_map = {}
   
   
2. 반복문
   :nums 리스트의 각 요소와 해당 인덱스를 가져와 반복합니다.
   for i, num in enumerate(nums):
   
   
3. 차이 값 검사
   :반복문에서 현재 값 num의 보완 값(target - num)이 딕셔너리 nums_map에 있는지 검사합니다.
   이 보완 값이 존재한다면, 그 값과 현재 값의 합이 target이 될 수 있다는 의미입니다.
   if target - num in nums_map:
   
   
4. 인덱스 반환
   :보완 값이 딕셔너리에 있다면, 해당 보완 값의 인덱스(nums_map[target - num])와 현재 인덱스 i를 리스트로 반환합니다. 이 두 인덱스는 조건을 만족하는 숫자들의 인덱스가 됩니다.
   return [nums_map[target - num], i]
   
   
5. 딕셔너리에 추가
   :보완 값이 딕셔너리에 없다면 현재 숫자와 인덱스를 nums_map에 추가합니다. 이를 통해 다음 반복에서 현재 값을 찾는 데 활용될 수 있습니다.nums_map[num] = i
   
   

예시

nums = [2, 7, 11, 15]와 target = 9일 때:

• 첫 번째 반복 (i = 0, num = 2):
  • target - num = 9 - 2 = 7이 nums_map에 없으므로 nums_map에 {2: 0} 추가
• 두 번째 반복 (i = 1, num = 7):
  • target - num = 9 - 7 = 2가 nums_map에 존재 ({2: 0}), 따라서 [0, 1] 반환

따라서 반환값은 [0, 1]입니다.

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, num in enumerate(nums):
            # print('[for] i= '+str(i)+", num= "+str(num))
            if target - num in nums_map:
                # print('return ['+str(nums_map[target - num])+', '+str(i)+']')
                return [nums_map[target - num], i] 
            # print('nums_map['+str(num)+'] = '+ str(i))
            nums_map[num] = i
            # print('----------------------')

            

# 출력
[for] i= 0, num= 2
nums_map[2] = 0
----------------------
[for] i= 1, num= 7
return [0, 1]

 

• nums = [2,7,11,15]이며, target = 9 이다.
• 첫번재 for문에서는 조건에 안맞아 if를 수행하지 않고, nums_map에 i와 num 값을 거꾸로 저장한다.
• 두번째 for문에서는 9 - 7 = 2 이기 때문에 첫번째 for문에서 nums_map에 저장된 nums_map[2]의 값을 사용한다.
• 그래서 정답인 [0, 1]이 출력된다.