[LeetCode] 1. Two Sum

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

Two Sum - LeetCode

내 풀이 1

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

어째선지 빠른데; test case가 적어서 그런가보다.. 좀만 늘어나도 엄청 느려질 풀이이다. O(n^2)이니까. 별로 좋은 풀이는 아니다.

내 풀이 2

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index = []
        # 몇번째 원소인지 알려주는 enumerate()
        for i, n in enumerate(nums):
            tmp = target - n
            if tmp in nums[i + 1:]:
                return nums.index(n), nums[i + 1:].index(tmp) + (i + 1)

 

주목 할 문법

• 특정 값이 있는지 검사하는 in
• 리스트 슬라이싱

리트코드 1번 문제인 만큼 쉽긴한데, 풀이1번처럼 하는것은 좋지 않은 풀이이다. 뺀 값을 조회하는것은 바로 생각해냈다. 책풀이는 이것저것 최적화를 하는 방법을 많이 알려준다. 이런 문제를 통해서 개선하는 방법을 배우는 것도 좋을 것 같다.

 

 

책 정보

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기