[leetcode] 1. Two Sum(easy)

이전에 푼 것인데 왜 새로울까..
그래서 시작하는 기록✒️
24.01.27
배열

(BOOK) 파이썬 알고리즘 인터뷰 - 박상길

🔷 leetcode의 장점

1. 문제 모아 보기가 좋다.
   

2. 내 정답의 runtime, memory별 %를 비교해서 볼 수 있다. 각 구역별 다른사람의 풀이와 함께.
   

3. 깃허브 commit 처럼 월별 참여 기록이 된다.
   

4. 힌트를 단계적으로 제공한다.

🔷Two Sum

문제

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

1. for문으로 풀기(나-느리다!)

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

⌛$O(n)$ = $O(N^2)$

2. enumerate로 시간 단축(남의 풀이)

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

• 한 번에 정답 찾기
• 첫 번째 수를 뺀 결과 키 조회(평균적으로 조회는 $O(1)$에 가능, 최악은 $O(n)$)

3-1. 첫 번째 수를 뺀 결과 키 조회

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]]

3-2. 구조 개선

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