[Leet Code Top 100] #217. Contains Duplicate

문제 정보

• Leet Code 문제 링크
• 난이도 : easy

 

해결 방법

첫 시도에는 하나의 수 라도 중복이 될 경우 true 이기 때문에 중복을 제거할 수 있는 수단 중 Set 을 사용해 구현했습니다. 코드는 간단했지만 생각보다 속도는 빠르지 않았습니다.

Discuss 탭에 있던 글을 몇 가지 확인해 보니 Set 대신 Object 로 구현할 경우 모든 nums 에 대해 순회하지 않고 중복되는 수를 만났을 때 종료하는 하기 때문에 nums 의 크기가 커질 수록 Object 가 유리함을 알 수 있습니다.

1,000 elements (Set is 7x faster):
Set: 0.15ms
Object: 1.02ms

10,000 elements:
Set: 0.87ms
Object: 0.88ms

100,000 elements:
Set: 10.91ms
Object: 7.58ms

1,000,000 elements (Object is almost 3x faster):
Set: 166.79ms
Object: 59.55ms

10,000,000 elements (Object about 5x faster):
Set: 3,575.32ms (3.5 seconds!)
Object: 678.08ms

 

소스 코드

// Leet Code
// #217. Contains Duplicate
// Success
// Runtime: 132 ms, faster than 27.83% of JavaScript online submissions for Contains Duplicate.
// Memory Usage: 49.2 MB, less than 10.70% of JavaScript online submissions for Contains Duplicate.

function main(){
    // Input
    nums = [1,2,3,1];
    // Output
    // true
    console.log(containsDuplicate(nums));
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
// var containsDuplicate = function(nums) {
//     const numSet = new Set(nums);
//     if(numSet.size === nums.length) return false;
//     return true;
// };

var containsDuplicate = function(nums) {
    const numObj = {};
    for(let idx = 0; idx < nums.length; idx++){
        if(numObj[nums[idx]] === true){
            return true;
        }
        numObj[nums[idx]] = true;
    }
    
    return false;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• Javascript - set vs. object