Week 2-1. [Hash Table] 219. Contains Duplicate II (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150 

Contains Duplicate II - LeetCode

주어진 리스트 내에 두 개의 서로 다른 인덱스 i와 j가 존재하여 nums[i]==nums[j]를 만족하면서 abs(i-j) <= k 라면, True를 반환하라.

• | nums | ∈ [1, 10^4]

 

🔎 어떤 식으로 접근했는가?

defaultdict를 사용하여 nums의 값을 key로, 인덱스를 value로 저장한다.

이 때 같은 값을 가진 요소들의 인덱스는 리스트 안에 누적된다.

 

이제 딕셔너리의 values를 순회하면서 절댓값이 k 이하인 i와 j가 있다면 True를 반환하고 종료한다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

딕셔너리를 이용하여 같은 값을 가진 요소들의 인덱스들을 초기화한다.

 

📝 의사 코드

dic = defaultdict(list)

enumerate(nums)를 순회하며:
	dic[x]에 i를 추가한다.
    
dic.values()를 순회하며:
	길이가 1보다 크면서 거리가 k보다 작으면:
    	return True
        
return False

 

🎯 구현 코드

from collections import defaultdict

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

        dic = defaultdict(list)
        for i, x in enumerate(nums):
            dic[x].append(i)

        for v in dic.values():
            if len(v) <= 1: continue # nums[i] == nums[j]인 i, j가 존재하지 않는 경우
            for i in range(len(v)-1):
                if abs(v[i] - v[i+1]) <= k: return True

        return False

만약 nums가 [1, 0, 1, 1]이라면, 딕셔너리는 아래와 같이 초기화 된다.

{
    1: [0, 2, 3],
 	0: [1]
}

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search로 시간복잡도는 O(n)이다.

 

✍️ 성능 회고

1초의 시간 제한을 갖는다고 할 때, O(n)의 시간 복잡도를 가진 코드에서 입력의 최대 크기 n은 대략 10^6이다.

문제에서 입력의 최대 크기는 10^5이므로 안정적으로 처리할 수 있다.

 

💡 무엇을/어떻게 개선할 수 있을까?

dic.values()를 순회하며 거리(절댓값)가 k 이하인 두 원소를 체크할 때의 로직을 개선하고 싶다.

abs(v[i]-v[i+1])로 모든 v를 체크하지 않고 한번에 구할수는 없을까?

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

set 자료구조를 활용한 풀이로, set 안에 항상 k개의 원소를 유지한다.

 

nums를 순회하면서, 특정 원소(nums[i])가 set 안에 존재한다는 것은 해당 원소(nums[i])와 set 안에 있는 원소들과의 거리가 k 이하라는 의미이다.

 

만약 set의 길이가 k+1이 된다면, set 안에서 nums[i-k] 원소를 제거한다.

(nums[i-k]는 가장 최근에 들어온 원소(nums[i])로부터 거리가 k인 원소로 가장 처음 들어온 원소를 의미한다.)

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

        if k == 0: return False

        st = set()
        for i in range(len(nums)):
            if nums[i] in st: return True
            st.add(nums[i])
            if len(st) == k+1:
                st.remove(nums[i-k])

        return False

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search로 O(n)의 시간복잡도를 가진다.

 

느낀 점

set 자료구조를 활용하여 set 안에 k개의 원소를 유지하는 방법은 정말 생각치 못했다.

 

"set은 순서를 보장하지 않는데, set 대신 리스트를 써야하는 것이 아닌가?" 싶었지만, set 내부에서 값이 nums[i-k]인 요소를 제거하면 되므로 순서를 보장할 필요가 없다.

 

따라서 중복을 제거해주는 set을 사용하는게 효율적이다.