leetcode 1. Two Sum 리트코드 1. 두 수의 합 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

leetcode.com/problems/two-sum/

 

입력: 정수 리스트, 정수 1개

출력: 정수 리스트

 

문제 요약: 리스트에서 두 개의 수를 더하면 target이 되는 원소의 인덱스를 리턴

유의 사항:

1. 두 원소의 값이 아니라 인덱스를 한다는 점

2. 조건을 만족하는 답이 딱 하나

3. 그리고 리스트의 길이 최대 1000개, 타겟 값 10**9 등 단위가 매우 크기 때문에 효율성에 신경을 써야 한다.

--> 리스트를 딕셔너리로 변환하자. 

생각 과정

1. 입력받은 리스트를 딕셔너리로 변환하고,

2. 딕셔너리내에 value 와 target - value가 있을 때,

3. value의 key 값과 target-value의 key값을 출력

풀이

딕셔너리로 변환했을 때 까다로웠던 것 중 하나는 인덱싱의 문제였다.

리턴해야 하는 것이 원소의 값이 아니라 인덱스인데 딕셔너리에서는 value 를 가지고 key를 인덱싱하는 것이 좀 귀찮다.

책을 참고로 했더니, key와 value의 위치를 바꾼 딕셔너리를 만들어서 이 문제를 해결하더라.

 

이렇게 만든 코드를 제출했는데, 결과는 wrong!

[3,3] 과 같이 리스트에 같은 값의 원소가 들어갈 경우, value, key 쌍의 딕셔너리를 만들면, 마지막 key만 value로 저장되고 만다.

다시 한 번 수정해서 통과된 코드는 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {v:k for k, v in enumerate(nums)}
        for k, v in enumerate(nums):
            if target - v in num_dict and k != num_dict[target-v]:
                return[k, num_dict[target-v]]