[LeetCode] - 두 수의 합

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

 

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

Two Sum - LeetCode

---

풀이) 

1. 브루트포스로 풀기 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    
    for i in range(len(nums)-1) :
    	for j in range(i+1 , len(nums)) :
        	if nums[i] + nums[j] == target :
            	return [i,j]

 

2. in을 이용한 탐색 

모든 조합을 비교하지 않고, 정답(타겟)에서 첫 번째 값을 뺸 값 (target - n) 이 존재하는 지 탐색하는 문제로 변경하여 풀이할 수 있다. 

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 )

 

여기서 더 나아가 수를 키로 하고 인덱스는 값으로 바꿔서 딕셔너리로 저장하면 키를 조회해서 정답을 즉시 찾아낼 수 있다

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

        nums_map = {}
        
        for i , n in enumerate(nums) :
            nums_map[n] = i 

        for i , n in enumerate(nums) : 
            # 만일 target - n 이 nums 에 포함되어 있고 해당 인덱스가 현재 인덱스와 동일하지 않은 경우 
            if target - n in nums and i != nums_map[target-n] :
                return [i , nums_map[target-n]]

 

---

🤔이 문제를 투 포인터로 풀 수 있을까? 

입력값인 nums는 정렬된 상태가 아니다. 투 포인터를 이용해 풀이를 하기 위해서는 정렬이 필요하다. 하지만 이렇게 하면 인덱스는 엉망이 된다. 이처럼 값이 아닌 인덱스를 찾아내는 문제는 정렬을 통해 인덱스를 섞어버리면 곤란하다.