Leet code #1 Two Sum > 수식의 역발상과 enumerate사용

문제. nums라는 array가 주어졌을 때, target 숫자의 합이 나오는 각 숫자의 순번(=인덱스)가 담긴 array를 반환하라

(단, 각 input에는 하나의 조합만 존재한다 -> 여러 조합이 가능한 경우 없음)

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

---

처음 접근 > nums의 변수를 앞에서부터 하나씩 더해보면서 target을 충족하는 숫자의 index를 반환하면 되지 않을까?

 

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

 

그래서 위와 같은 코드를 짜봤는데 계속 output에서 중복된 index를 반환하고 시간도 많이 걸렸다

 

Input
[2,5,5,11]
10
Output
[1,2,2,1]
Expected
[1,2]

 

--> 다른 사람들의 풀이를 보고 깨달은 점은 문제 자체가 target값을 만족하는 숫자들과 각각의 index값이 함께 따라오므로 딕셔너리 형태를 이용한 Hash 문제임을 파악해야 하는 것이었다..... Hash문제를 그렇게 풀어놓고 보자마자 생각이 안 떠오르다니.....ㅜㅠ 그리고 index값을 활용해야 한다 --> enumerate함수를 효과적으로 사용할 수 있다는 말,,,

 

---

모범 답변)

def twoSum(self, nums, target):
	di = {}
    for i, n in enumerate(nums):
    	m = target - n
        if m in di:
        	return [di[m],i]
        else: di[n] = i

이 풀이는 enumerate 를 사용해서 index 값을 쉽게 구하고 di 딕셔너리에 숫자: 인덱스를 저장했다

하지만, 신선했던 관점은 target = m + n 을  m = target -n 이라는 식으로 재해석해서 

 

target을 만족하는 m과 n을 찾자 ------> target과 n을 정해놓고 이 값을 충족하는 m을 구하자!!!는 역발상

기존 방식은 m과 n을 각각 찾기 때문에 비효율적인 중첩이 발생할 수 밖에 없지만 새로운 방식의 경우 자연스럽게 target-n을 만족하는 m이 나타나면 계산을 멈추고 바로 [d[m],i] 즉 m의 인덱스와 n을 가져온 인덱스를 반환하도록 했다.

 

쉬운 난이도의 문제에 해당하지만 코딩 문제는 참 배울 점이 많은 것 같다 :)