[LeetCode] 217. Contains Duplicate (JS)

https://leetcode.com/problems/contains-duplicate/

Contains Duplicate - LeetCode

핵심 아이디어

• hashSet `has()`로 이전에 나왔던 값인지 1회당 O(1) 시간에 찾기

 

복잡도

• 시간 복잡도: O(n)
  
  • hashSet.has() O(1) * n개 원소
• 공간 복잡도: O(n)
  
  • hashSet()에 n개의 데이터를 저장하는 데 드는 공간

 

설명

배열 안에 중복된 요소가 있는지 검사하는 문제이다. 각 요소를 순회하며 hashSet에 저장하고 hashSet has 연산이 O(1) 시간이 걸린다는 점을 이용하여 O(n) 시간에 풀 수 있다. 배열에서 요소를 찾는 연산이면 회당 O(n) 시간이 걸려 총 O(n^2)  시간이 걸리기 때문에 hashSet을 쓰는 것이 유리하다.

다른 풀이로는 sort를 이용하는 방법이 있다. sort 후 다음 요소가 현재 요소와 같은 경우가 있는지 검사하면 된다. 이 경우 시간은 O(nlogn) 시간이 걸리지만, 추가적인 공간을 필요로 하지 않아 공간 복잡도가 O(1)이라는 장점이 있다. 그러나 일반적인 상황에서는 O(n)정도 공간을 희생하고 시간을 더 줄이는 hashSet이 더 유리할듯 하다

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const set = new Set();
    
    for (num of nums) {
        if(set.has(num)) {
            return true
        }
        set.add(num);
    }
    
    return false;
};

 

유튜브 NeetCode 해설 영상

 

여담

• 배열에서 중복을 찾는다니 꽤나 실용적인 문제같다
• 전에 two sum 문제 풀어봤던 경험으로 이 문제도 브루트 포스 따위가 아닌 해시를 먼저 떠올릴 수 있었다 ㅎㅎ
  • 현업에서 O(n^2) 쓰기 꺼려지는 게 본능적으로 느껴져서 그랬을지도? 아마 현업에서 이런 문제를 만났다면 주로 중복 판단보다는 제거가 문제일테니 냅다 array를 Set으로 받거나, 아예 Set에서 입력 하나하나 받았을 것 같다
• JS Set은 hashSet인가?
  • Stack overflow 답변글에 따르면, ECMAScript 스펙에 hash table 또는 sublinear time( O(n) 미만, O(logn) ) 이 걸리는 방식으로 구현하라고 정의되어 있다
  • 따라서 별다른 이유가 없다면 브라우저는 hash table로 구현했을 것이고, 아니라고 한들 array.includes() 보다 좋은 성능을 보장하니 안 쓸 이유는 없다고 생각한다.