[LeetCode] Two Sum

문제 링크 >> https://leetcode.com/problems/two-sum/

 

 

📋 문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

👉 입출력 예제

Example 1:

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

 

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

 

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

 

📝 풀이

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]

 

처음에는 예제만 보고 풀다가 연속된 수 중에서 합이 target이 되는 경우를 고르는 줄 알고 많이 틀렸다.

해시 예제인걸 알면서도 앞에서 이미 많이 틀려서 이제는 그냥 풀고 봐야겠다는 식으로 모든 경우의 수를 살펴보는 brute force 방식으로 풀었다.

nums 배열의 요소 중 2개를 고르는 모든 경우의 수 중에서 그 둘의 합이 target이 될 때 해당하는 인덱스 번호들을 반환하는 것이다.

 

물론 이렇게 풀었더니 Runtime이 무려 5070ms나 나왔다.

이것을 좀 개선해보고자 해시맵을 이용해 문제를 푸는 방식을 이해해 보기로 했다.

 

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

        for i in range(len(nums)):
            hashmap[nums[i]] = i
            
        for i in range(len(nums)):
            temp = target - nums[i]
            
            if temp in hashmap and hashmap[temp] != i:
                return [i, hashmap[temp]]

 

먼저 hashmap으로 쓰일 빈 딕셔너리를 선언했다.

이후 for문을 돌며 nums의 요소들을 hashmap에 저장하는데 key는 nums의 요소이고 value는 해당 요소의 인덱스 번호이다.

 

hashmap의 저장이 끝났다면 다시 nums의 길이만큼 for문을 돈다.

for문 안에서 둘의 합이 target이 되는 요소의 인덱스 번호들을 추출하는데 그 원리는 다음과 같다.

1. target에서 현재 요소 값을 뺀 것을 temp에 저장한다.
2. temp가 hashmap의 key들 중에 있는지 확인한다. 
3. temp가 hashmap의 key에 속하고 이 값이 현재 요소가 아니라면 현재 인덱스인 i와 temp를 key로 가지는 값의 인덱스(value)를 리턴한다.

이러한 hashmap을 이용하는 방식으로 풀었더니 5070ms이던 런타임이 60ms로 줄었다.