LeetCode 1번 문제

Park Choong Ho·2021년 10월 23일

1.문제에 대한 이해

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.

정수가 담긴 리스트와 타깃 정수가 주어지고 리스트에서 2개를 골라 더해서 타깃 정수가 되면 해당 수들의 index값을 반환하면 되는 문제입니다. 하나의 케이스에는 정확히 답 하나만이 존재한다고 합니다. 그리고 index를 반환할 떄의 순서는 상관없습니다.

2 <= nums.length <= 104

-10^9 <= nums[i] <= 10^9

-10^9 <= target <= 10^9

Only one valid answer exists.

2. 해결 계획의 작성

우선 방법 하나는 리스트를 2중으로 돌면서 모든 경우의 수를 체크해보고 그 중에 타깃 정수를 만족하는 정수 2개가 리스트에 있으면 이를 반환하는 방법입니다. 하지만 이 방법은 시간 복잡도가 O(n^2)가 됩니다. 문제 권장 사항을 보면

Can you come up with an algorithm that is less than O(n^2) time complexity?

라고 되어 있습니다. 시간복잡도를 O(n^2)보다 작게 만들라고 권장하고 있습니다. 우선 문제는 2개 문자를 더해서 타깃 정수를 만족하는지 확인하는 로직이 있어야합니다. 만약 [6, 8, 9 , 10]이 리스트이고 타깃 정수가 15라고 했을 때 6에 대한 값 9를 저장해 놓고 9에 갔을 떄 저장해놓은 9와 대조해서 일치한다면 리스트를 한번만 순회할 수 있습니다. 또한 9를 저장해 놓고 9와 바로 비교해서 시간 복잡도를 줄일려면 이 비교하는데 있어 시간복잡도가 O(1)인 딕셔너리를 사용하여 문제를 풀 수 있습니다.

그럼 여기까지 해서 문제 해결은

딕셔너리를 만든다.
타깃 정수에서 현재 정수를 뺀다.
그 값이 만약 딕셔너리에 있으면 답을 반환한다.
없으면 그 다음 정수로 간다.

이 4가지 단계로 해결하면 될것 같습니다.

3. 계획의 실행

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        val_dict = {}
        
        for i in range(len(nums)):
            target_num = target - nums[i]
            if nums[i] in val_dict:
                return [val_dict[nums[i]], i]
            else: 
                val_dict[target_num] = i

for문을 보면 찾으려는 타겟 숫자(위 예시에서 9)가 있으면 해당 index와 현재 index를 즉시 반환하고 없으면 해당 index를 value, 타겟 숫자를 key로 가지게끔 해서 딕셔너리에 집어 넣습니다. 여기서 if nums[i] in val_dict가 시간 복잡도가 O(n)이면 이 코드도 O(n^2)가 됩니다. if nums[i] in val_dict의 시간 복잡도는 어떻게 될까요?