문제

주어진 정수 배열 nums와 정수 target에 대해, 덧셈하여 target을 만들 수 있는 배열 안의 두 수의 인덱스를 반환하여라.

정확히 하나의 답이 존재하며, 같은 원소를 두 번 사용하지 않을 수 있다.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]

풀이

당연히 생각해 볼 수 있는 풀이 방법은 brute-force이다. 하지만 이 방식으로는 시간 초과가 발생한다.

문제에서 분명히 하나의 답이 존재한다고 했으므로, 우리는 현재 숫자에 대한 나머지 후보가 될 수 있는 dictionary를 이용하여, 값을 찾아낼 수 있다.

이를 Python으로 구현하면 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}
        
        for idx, num in enumerate(nums):
            
            #현재 숫자 num에 대한 나머지 계산
            complement = target - num
        
            # 나머지가 dictionary안에 있을 경우.
            if complement in nums_dict:
                return [idx, nums_dict[complement]]
            
            #현재의 숫자를 key로 index를 value로 설정(현재의 값은 미래의 나머지가 될 것이므로).
            nums_dict[num] = idx