[LeetCode] 1. Two Sum

1. 문제

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

2. 접근 방법

이 문제는 nums의 값 들 중 두 수를 골라 더했을 때 target값이 나오는 두 수의 인덱스를 찾는 문제이다.

 

사실 for문을 중첩해서 풀이할 수도 있지만 그렇게 될 경우 시간 복잡도가 O(n2)이기 때문에,

dict를 사용해서 풀이를 진행했습니다.

 

key에는 숫자 값을 넣고, 해당 value에는 그 숫자의 인덱스를 넣습니다.

 

for문을 사용해 타겟에서 숫자를 뺀 값이 dict의 key에 존재한다면, 해당 key의 value인 인덱스 값을 뽑아내면 됩니다.

 

근데 이 때 주의해야할 점이, 타겟에서 숫자를 뺀 값이 dict의 key에 존재하지만, 자기 자신이면 안됩니다.

(두 수 여야하기 때문)

 

처음에 이 부분을 고려하지 않았더니

틀린 테스트케이스를 알려주고, 친절해서 조와,,

이런 테스트 케이스에서 걸리더라구용?

 

그래서 idx 값을 확인하는 과정도 추가해줘야합니다.

 

----

 

처음에는 위의 방법처럼 1. dict에 집어넣기, 2. nums를 순회하면서 다른 인덱스 찾기 로 했는데요

이렇게 안하고

집어넣으면서 찾는 방법도 있습니다.

 

1. nums를 순회하면서 dict를 사용해 다른 인덱스 찾기

2. 없는 경우 현재 num을 dict에 집어 넣기 (key = num, value = index)

 

3. 코드

Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}
        for i, num in enumerate(nums):
            if target - num in nums_dict:
                return i, nums_dict[target-num]
            nums_dict[num] = i

4. 마치며

요즘 dict에 빠졌습니다