3 분 소요

Hash Table

문제

문제 링크

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.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

스스로 고민

접근법

  • 배열에서 두 수를 추출한 뒤에 둘을 합했을 때 타겟 넘버 값을 만들 수 있는 각 요소의 인덱스를 추출하면 된다.
  • 무지성으로 하기 전에 문제를 자세히 읽지 않아 삽질한 경험이 많았기 때문에 문제를 잘 살펴 보았는데 요소에는 음수도 나올 수 있다.
  • 또한 다행히 요소들간에 중복은 없다.
  • 이전에 투포인터 패턴을 풀다가 다른 사람들의 방법을 보던 중 같은 문제를 해시맵을 활용해서 풀었던 게 생각나서 그걸로 결정

의사코드

  • 우선 모든 값을 딕셔너리에 다 넣어준다.
  • 첫 번째 요소를 뽑아서 타겟 값과 계산 후 매칭 되는게 있다면 인덱스를 반환
  • 없다면 두 번째 요소로 넘어가서 계속 진행

구현 코드

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        num_dict = {}

        for i, num in enumerate(nums):

            complement = target - num

            if complement in num_dict:

                return [num_dict[complement] , i]

            num_dict[num] = i

시간 복잡도와 공간 복잡도

시간 복잡도:

  • 반복문이 nums 리스트의 길이인 n번 실행된다. 각 반복에서 수행되는 작업은 O(1) 시간이 걸린다.
  • 딕셔너리에서 특정 값을 검색하는 작업도 O(1) 시간이 소요된다. 따라서 전체적으로 twoSum() 메서드의 시간 복잡도는 O(n)다.

공간 복잡도:

  • num_dict 딕셔너리는 최악의 경우 n개의 숫자를 저장해야 할 수 있으므로 O(n)의 공간이 소요된다.
  • 나머지 변수들은 상수 개수의 메모리를 사용하므로 공간 복잡도에 영향을 주지 않는다.
  • 따라서 전체적으로 공간 복잡도는 O(n)다.

회고 과정

  • 이전에 다른 사람들이 어떻게 했는지 봐두었던 경험 때문에 정말 쉽게 풀었다.
  • 이게 순전히 내 실력은 아직 아닌거 같다. 하지만 이렇게 계속 레고처럼 쌓다보면 분명히 발전이 있을 거 같다.
  • 다른 사람코드가 기억이 나서 이렇게 문제를 풀 수 있었던 이유는 다른 사람들의 접근 방법과 코드를 이해하려고 노력해서 기억에 남았던 것 같다.
  • 문제를 푸는 것도 중요하지만 다른 사람들의 코드를 보면서 배울 수 있는 점이 있는지 항상 고민해보는 게 이번에 정말 큰 도움이 되었던 것 같다.

    다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

  • 와우 버그인가? 정말 손 안 대고 코 잘풀었다.
  • 첫 시도만에 이런 적이 처음이라 진짜 좋았다 🥳
  • 솔직히 여태까지 시간 복잡도 위주로 봤었는데 이번에는 메모리 부분으로!
class Solution:
    def twoSum(self,nums: List[int], target: int) -> List[int]:
        l = len(nums)
        a = [0,0]
        if(l>=3):
            for i in range(l-1):
                for j in range(i+1,l):
                    x = nums[i] + nums[j]
                    if(target==x):
                        a[0] = i
                        a[1] = j
        else:
            a[0] = 0
            a[1] = 1    

        return a

시간 복잡도:

  • twoSum() 메서드에서 중첩 반복문을 사용하여 nums 리스트를 순회하므로 이중 반복문이 사용된다.
  • 첫 번째 반복문은 최대 n-1번 실행되며, 두 번째 반복문은 최대 n-1, n-2, …, 1번 실행된다. 따라서 이중 반복문의 실행 횟수는 n-1 + n-2 + … + 1 = n*(n-1)/2 이며, 이는 O(n^2) 다.
  • 따라서 전체적으로 twoSum() 메서드의 시간 복잡도는 O(n^2) 다.

공간 복잡도:

  • 입력된 숫자 리스트와 상수 개수의 변수 이외에 추가적인 데이터 구조를 사용하지 않는다.
  • 리스트 a는 결과를 저장하는 용도로 사용되지만, 이는 입력 크기에 상관없이 고정된 크기를 가지므로 공간 복잡도에 큰 영향을 미치지 않는다.
  • 따라서 전체적으로 공간 복잡도는 O(1) 다.

종합하면, 주어진 코드의 시간 복잡도는 O(n^2), 공간 복잡도는 O(1) 다.

  • 음.. 속도가 별로 중요하지 않고 메모리가 매우 제한적으로 사용되어야 하는 임베디드 시스템에는 위와 같은 코드가 유용할 수 있다고 생각했다.

댓글남기기

참고