[Q. 07] 두 수의 합

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

 

처음 이 문제를 접하게 되면, 모든 경우의 수에 대한 조사를 할 것이다. 나 또한 그렇게 해결하였지만 이는 n의 제곱의 경우의 수로 매우 비효율 적이다. 그래서 파이썬으로 이러한 최적화 문제를 풀 때 가장 유용한 것은 딕셔너리를 이용하는 것이다.

 예를들어 [2,3,7] 에서 3이라는 값이나 인덱스를 찾으려면 in이나 index 함수를 사용하여야 하는데 이는 O(n)이다. 하지만 이를 딕셔너리로 변환하여 'Dict[값] = 인덱스' 형태로 저장하면 해당 값의 인덱스를 찾거나, 해당 값이 있는지 확인하는데 걸리는 시간은 O(1)이 된다.

 이를 활용하여 이 문제를 해결해보자.

 

먼저, 딕셔너리 형태로 배열을 정리한다.

num_dict = {}

for i, n in enumerate(nums):
    num_dict[n] = i

 

보는 것과 같이 'Dict[값] = 인덱스' 형태로 딕셔너리를 생성하였다. 

그 다음, 'target - 값' 이 딕셔너리에 존재하는 지를 확인하면 덧셈하여 만들 수 있는 배열의 두 숫자가 될 것이다.

for i, n in enumerate(nums):
    if num_dict.get(target - n) != None and i != num_dict[target - n]:
        return i, num_dict[target-n]

 

여기서 i != num_dict[target-n]을 확인하는 이유는, 같은 인덱스에 있는 값을 2번 사용 할 수도 있기 때문에 그것에 대한 예외를 설정해 주는 것이다.

 

전체 코드는 다음과 같다.

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

        for i, n in enumerate(nums):
            num_dict[n] = i

        for i, n in enumerate(nums):
            if num_dict.get(target - n) != None and i != num_dict[target - n]:
                return i, num_dict[target-n]