[리트코드] Two Sum(python)

리트코드, Two Sum_두 개의 합

 

문제

1. 주어진 정수의 배열 nums와 정수 target에 대해 더해서 target이 되는 두 개의 숫자 인덱스를 반환하라.
2. 각 입력에 대해서는 오직 하나의 정답만이 존재하고, 하나의 원소를 두 번 사용할 수 없다.
3. 정답은 어떤 순서로 반환되어도 상관 없다.

입출력 형태

입출력 예시

 

- 예시 1번

  - nums에 입력이 [2, 7, 11, 15] target이 9로 주어졌다.

  - 문제 조건에 따라 nums에서 합이 9가 되는 원소의 인덱스를 반환하면 된다.

  - 2와 7을 더했을 때 9가 되므로 2의 인덱스인 0과 7의 인덱스인 1을 반환하면 된다.

- 예시 3번

  - nums = [3, 3], target = 6

  - 문제 조건 2에 의해 동일한 원소를 두 번 사용하면 안 된다.

  - 따라서 첫 번째 3의 인덱스인 0과 두 번째 인덱스인 1을 반환하면 된다.

풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """ brute force -> 4076ms
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        """   

        # dict -> 60ms
        dicts = collections.defaultdict(int)
            
        for i, num in enumerate(nums):
        	# 타겟에서 하나의 원소를 뺀 것이 딕셔너리에 존재하며, 동일한 인덱스가 아닐 때
            if target - num in dicts and i != dicts[target - num]:
                return [i, dicts[target - num]]
            dicts[num] = i

 

- 여러 방법이 존재하지만 2가지의 방법으로 풀었다.

- 첫 번째 방법은 brute force 방법이다.

  - 배열에서 원소 2개씩을 골라 합하고, 해당 합이 target과 동일할 때 해당 인덱스를 반환한다.

  - 구현이 쉽지만 O(n^2)로 시간 복잡도가 매우 높다.

- 두 번째 방법은 dictionary를 활용하는 방법이다.

  - dictionary를 선언하고, nums에 들어있는 숫자를 key로 해당 인덱스를 value로 저장한다.

  - nums를 순회하며 target에서 nums의 원소를 빼고, 해당 원소가 dictionary에 존재하면서도, 동일한 인덱스가 아닐 때 각 인덱스를 반환한다.

  - dictionary의 경우 조회하는데 시간 복잡도가 O(1)이고, 최악의 경우 O(n)이기 때문에 brute force에 비해 훨씬 빠르게 수행된다.