코딩테스트 공부

leetcode 문제 - easy

Two sum :

python3

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

My solution

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        remain = 0
        for i in range(len(nums)):
            remain = target - nums[i]
            if remain in nums:
                for j in range(i+1, len(nums)):
                    if remain == nums[j]:
                        return [i, j]

    
    def isLarger(self, num, target):
        return num > target

대충 O(nlogn) 정도 되지 않을까 했는데 다시 생각해보면 O(n^2)인거 같다. 조금 더 빠른듯 하긴 하지만 runtime은 900ms.
Dictionary를 사용하면 10배 빠르게 구현 가능하다.

Better Solution

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

enumerate 를 사용하여 list를 iterate 하면 index값을 같이 가져올 수 있다.
index값을 value, 숫자를 key로 mapping 하여 dictionary를 만들면 훨씬 빠르게 구현할 수 있다. dictionary key 찾는것도 n time operation이 아닌가 싶긴 하지만 dictionary는 key값을 hash로 저장하기 때문에 list보다 훨씬 빠르다.

Hash 함수를 잘 기억하자. 딕셔너리 짱짱.
화이팅.