LeetCode - 1번 Two Sum

LeetCode 1번 Two Sum

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

내 풀이

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]

어제 풀었던 백준 블랙잭 문제처럼 완전탐색 방식으로 접근했다.

공간 복잡도 점수는 상위 20%쯤인데 시간 복잡도가 O(n²)이 되면서 하위 10%쯤 됐다… 다른 사람은 어떻게 풀었나 봤다. 가장 좋아요를 많이 받은 파이썬 답변이다.

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

1. 빈 딕셔너리를 먼저 만들어주고 주어진 리스트를 enumerate 함수를 써서 반복문을 돌린다.
2. n이라는 변수에 target(합)과 요소를 뺀 값을 대입해준다. 이 n이 찾아야 할 값이다.
3. 딕셔너리 h에 n이 없으면 딕셔너리에 저장한다. key는 요소, value는 nums 리스트 안에서의 인덱스값이다. (dictionary_name[key]=value)
4. 딕셔너리 h에 n이 있으면 딕셔너리 내에서 value, 즉 리스트 내에서 n의 인덱스값과 i의 인덱스값을 출력한다.

WOW… 어떻게 이렇게 생각하지. 코드 이해하는 데에도 한참 걸렸다. 여러 가지 자료구조를 어떻게 다루는지 머리에 잘 정리해놔야 이렇게 쓸 수 있겠지.