1 분 소요

Hash Table

문제

문제 링크

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

    스스로 고민

접근법

  • 처음에 무슨 소리인가 했는데 배열안에 K 값이 있고 그 K 값이랑 같은 요소들의 인덱스 값을 마이너스 했을 때 K 값보다 같거나 작으면 True를 반환하면 된다.
  • 이전에 사용했던 해시맵을 좀 변형해서 사용하면 될거 같았다.
  • 역시 배열 조건에는 음수가 포함된다.

의사코드

  • 이전에 사용했던 해시맵을 활용했다.

구현 코드

class Solution:

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        num_dict = {}

        for i, num in enumerate(nums):
            complement = num

            if complement in num_dict:

                if abs(i - num_dict[complement]) <= k:
                    return True

            num_dict[num] = i

        return False

시간 복잡도와 공간 복잡도

시간 복잡도:

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

공간 복잡도:

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

회고 과정

  • 패턴을 공부하라는 게 무슨 소리인지 이해가 되었다.
  • 익숙한 패턴이 있으니까 해당 패턴으로 응용해서 푸니까 정말 쉽게 풀었다.

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

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        #direct, it is a easy problem
        dic = dict()
        for i,n in enumerate(nums):
            if n in dic and i-dic[n]<=k: return True
            dic[n] = i
        return False
  • if 문이 두 개고 따로 추가 조건이 없을 경우에 and로 묶어 버리면 되는데 왜 여태까지 이렇게 생각을 못 한걸까 😂

댓글남기기

참고