딕션어리 활용해보기(Two sum)

문제

 

접근방법

원래는 완전 탐색(하나하나 탐색하기)식으로 문제를 풀었지만 이제는 접근을 똑똑하게 해보자.

컴퓨터가 아니라 암산으로 이 문제를 푼다고 하면 저 숫자들을 머리속에 저장해놓고 딱 한번만 보면서 풀 수 있을 것이다.

컴퓨터 상에도 메모리라는 머리속이 있기 때문에 거기에 저장해놓고 푼다고 생각하면 된다

풀이

def two_sum(nums, target):
  memo = {} # 딕션어리 만들기
  for v in nums:
    # nums를 돌아가면서 딕션어리에 저장 
    # 이때 키값은 nums이고 벨류값은 1
    # O(1)의 시간복잡도로 바로 키값 조회 가능
    memo[v] = 1 
    
    #--------여기까지가 딕션어리저장----------
    
  for v in nums : 
    # v 값이 4이고 target이 14일때 필요한 숫자를 구하는 코드
    # 만약 needed_number가 딕션어리에 있다면 바로 True 리턴할 수 있음(즉 두개의 숫자를 더해서 target이 나올 수 있다.)
    needed_number = target - v
    if needed_number in memo:
      return True
    
  return False

첫번째 for 문 O(1)

두번째 for 문 O(1)

그래서 이 풀이 방식의 시간 복잡도는 O(n)

2023.12.06 - [coding test] - Two Sum

Two Sum

여기서 우리가 풀었던 시간 복잡도를 생각해보면 혁신적인 일이다.

하지만 이렇게 로직을 작성하게 되면 같은 숫자를 두번 사용하게 되는데 아마 enumerate와 인덱스를 사용하면 체크를 할 수 있을 것 같다

def two_sum(nums, target):
  memo = {}
  for i, num in enumerate(nums):
    needed = target - num
    if needed in memo:
      return [memo[needed], i]
    memo[num] = i