[Q7] 두 수의 합

[리트코드 1] Two Sum

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

 

처음 이 문제를 보았을 때, 나는 모든 경우의 수를 다 비교해가며 정답을 도출했었다.

 

하지만, 코테 볼 때 항상 효율성에서 틀려버린 경험을 바탕으로 책을 읽어보니 매우 효율적인 방법이 있음을 알 수 있었다.

 

먼저, 다음과 같은 배열이 있다고 가정하자.

nums = [1, 3, 6, 8, 5]

 

이 배열에서 숫자 6의 위치를 찾는 방법은 find 함수를 사용하는 것이다. 하지만 이는 시간복잡도가 O(n)이다.

 

하지만, 다음과 같이 배열의 인덱스와 숫자를 딕셔너리로 구현하여 참조하면 시간복잡도를 O(1)로 줄일 수 있다.

nums_dict = {}

for i, num in enumerate(nums):
	nums_dict[num] = i

 

이제 문제를 풀어보자.

def twoSum(self, nums: List[int], target: int) -> List[int]:

    nums_dict = {}

    for i in range(len(nums)):
        nums_dict[nums[i]] = i

    for i, num in enumerate(nums):
        if target - num in nums_dict and i != nums_dict[target-num]:
            return [i, nums_dict[target-num]]

 

nums 배열을 순회하며,

target에서 해당 인덱스의 숫자를 뺐을 때 그 수가 nums_dict의 key값으로 존재하고 그 인덱스가 현재 인덱스와 같이 않을 때

정답을 반환하는 것이다.

 

위에 코드에서 만약 target-num의 값이 리스트에 있는지 확인하기 위해 find 함수를 사용했다면 시간 복잡도가 O(n)이 소모되지만,

리스트를 딕셔너리 형태로 바꾼 뒤 값을 찾으면 시간복잡도를 O(1)로 줄일 수 있다.