1. Two Sum (Easy) [Python]

문제

 

생각 방식

Brute Force로 풀자면 for loop을 두 번 써서 풀면 된다. 

근데 더 Time complexity가 좋은 코드를 어떻게 짜면 좋을까?

 

💻 일단 Brute Force로 작성한 코드

 

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

 

전에 풀었던 문제를 토대로 HashMap을 사용한다면 좀 더 좋다는 것을 알고 있지만 어떻게 짜야 할지 고민이 많았다

힌트를 보고 조금 생각을 하니 되게 간단했다 [좀 더 다양한 시각으로 보면 된다...]

*💡Hint: diff = target - num

 

여기서 enumerate()를 사용하는데,

enumerate()는 iterator이지만 index와 element를 같이 리턴해준다고 학교에서 배운 기억이 났다.

 

💻 다시 작성한 코드

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {}
        for idx, num in enumerate(nums):
            diff = target - num
            if diff in hashMap:
                return [hashMap[diff], idx]
            hashMap[num] = idx
        return

 

해설

hashMap에는 value 그리고 index가 있을 예정

첫 번째 test case를 예를 들어서 루프를 뜯어보면

 

1st loop (idx = 0, num = 2):

* diff = target - num = 7, 우리가 찾아야 하는 숫자는 7이다

* 7은 우리 hashMap에 아직 없다

* 그러므로 우리는 hashMap[num] = idx를 통해 value인 2를 추가해주고 index는 0이라는 것을 추가해준다

 

2nd loop (idx = 1, num = 7):

* diff = target - num = 2

* 2는 우리 hashMap에 있다

* 그러므로 return을 해주면 깔끔하게 해결된다

hashMap[diff] 는 아까 저장한 index 0이 된다, 그리고 지금 idx는 1 그래서 return 값은 [0,1]이 된다

 

 

결과