[LeetCode] #1. Two Sum (python)

문제

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

Two Sum - LeetCode

주어진 숫자 리스트에서 더하면 target 값이 되는 두 수의 인덱스 값을 리스트로 반환해야 하는 문제다.

 

예시 입출력

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

 

 

풀이

 

내 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        if len(nums)==2:
            return [0,1]
        
        for i in range(len(nums)-1):
            start=i
            for j in range(start+1, len(nums)):
                if start<j and nums[start]+nums[j]==target:
                    return [start,j]

 

그냥 하나씩 비교해가면서 반복문을 사용해서 풀었다. 그 결과 4592ms 걸렸다.

 

책 풀이

1. in을 활용한 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, n in enumerate(nums):
            complement = target - n

            if complement in nums[i + 1:]:
                return [nums.index(n), nums[i + 1:].index(complement) + (i + 1)]

target에서 첫번째 값을 제외한 값이 있는지를 찾는다.

enumerate는 인덱스와 원소를 동시에 접근할 수 있다. enumerate는 인덱스랑 값을 할당해주기 때문에 i에는 인덱스, n에는 값이 할당된다.

여기서 return할 때 끝부분 index에 i+1을 하는 이유 : index를 찾을 때 범위를 nums[i+1]로 했기 때문이다.

 

2. 딕셔너리를 활용한 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i

        # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return [i, nums_map[target - num]]

2번 풀이와 같이 첫번째 수를 뺀 결과를 찾는 것인데 숫자를 딕셔너리의 키, 인덱스를 값으로 사용하는 방식이다.

target에서 첫번째 값을 빼고 해당 키의 값(인덱스)이 같은 인덱스가 아닌 지 확인하고 반환한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰