리트코드 - Two Sum

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

Two Sum - LeetCode

문제 내용

정수 숫자 배열 nums와 정수 target이 주어졌을 때, target에 합산되는 두 숫자의 인덱스를 반환한다.
각 입력에 정확히 하나의 해가 있다고 가정하고 같은 요소를 두 번 사용할 수 없다.
어떤 순서로든 답을 반환할 수 있다.

 

풀이 과정

1. 처음에는 brute-force한 방식부터 생각했다. 

• 처음에는 각 리스트를 순회하면서 배열의 요소(숫자)를 변수에 저장한다.  - for idx, num in enumerate(nums)
• 그리고 target에서 해당 요소(num)를 뺀 다음 0보다 클 경우, 해당 요소의 다음 인덱스부터 순회해서 일치하는 값을 찾는다

하지만 위와 같이 생각했을 때는 반복문을 이중 순회하므로 시간 복잡도가 O(n^2)이 될 것이기 때문에 제외했다.

 

2. 딕셔너리를 활용한 방식을 생각했다.

• 딕셔너리를 생성해서 {요소 : 인덱스}의 형태로 저장해 놓으면 해당 요소를 키로 갖기 때문에 요소의 값만 알아도 O(1)의 시간복잡도로 인덱스를 알 수 있게 된다.
• 그리고 0번째 인덱스부터 target과 뺀 후 해당 값을 key로 가진 value가 인덱스이므로 반환 값에 추가했다. 
• 이때 동일한 요소는 두 번 사용할 수 없는 조건이 있으므로 동일 인덱스인지 확인하여 중복 여부를 확인했다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict_nums = {num : idx for idx, num in enumerate(nums)}
        for idx, num in enumerate(nums):
            find_num = target - num
            if find_num in dict_nums and dict_nums[find_num] != idx:
                return [idx, dict_nums[find_num]]

 

참고 내용

https://kadensungbincho.tistory.com/19

파이썬 딕셔너리 루프 - 파이썬 딕셔너리 순회하기 (Python Dictionary Iteration)

https://security-nanglam.tistory.com/427

[python] List to Dict (리스트를 딕셔너리로 변환) 총 정리!!