[LeetCode] Contains Duplicate (3가지 풀이방법)

문제 : 

 

배열 nums의 숫자들 중 하나라도 중복이 있는 경우 true를 return. 중복 여부만 판단하면 되는 문제라 Set()을 활용해 풀기로했다.  

 

풀이 : 

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const containsDuplicate = function(nums) {
    const newArr = [...new Set(nums)];
    
    return !(newArr.length == nums.length);
};

Runtime: 81 ms

Memory Usage: 56.6 MB

 

nums의 중복을 제거한 newArr를 만들어 두 배열의 길이를 비교해준다.

 

 

정답은 바로 맞췄지만, runtime이 생각보다 더 나와서 다른 방법으로 풀어보기로

 

풀이 2 : 

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const containsDuplicate = function(nums) {
    const newArr = [];
    
    for (let i = 0; i < nums.length; i++) {
        const isIncluded = newArr.includes(nums[i]);
        
        if (isIncluded) {
            return true;
        } else {
            newArr.push(nums[i]);
        }
    }
    
    return false;
};

Runtime: 5713 ms

Memory Usage: 51.9 MB

 

주어진 배열 nums를 for문을 돌려 배열 내에 있는 값이면 true를. 없는 값인 경우 newArr에 추가해주는 형태로 작성해보았다. 

 

최초의 답안보다 한참 못 미친다.

우수답안 풀이 1

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const hashMap = {};
    for (let i = 0; i < nums.length; i++) {
        if (hashMap[nums[i]] !== undefined) return true;
        hashMap[nums[i]] = nums[i];
    }
    return false;
};

 

내 답안 2와 크게 다를 것 없어 보이는데 배열과 객체에 그렇게 큰 차이가 있었던 걸까?

 

 

데이터의 양이 방대해질 수록 object key-value를 활용하는 것이 더 빠르다고 한다. LeetCode의 테스트 케이스가 그렇게 방대하지는 않을 것 같은데 어떤 차이가 있는지 ChatGpt에게 물어 보았다. 

 

 

object에서 key-value로 찾는 경우는 시간복잡도 O(1)이지만, include를 통해 찾는 경우 O(n^2)가 소요된다. 

 

ChatGpt 이 똑똑한 녀석... 앞으로도 잘 이용해주마 

 

우수답안 풀이 2

 

상위 랭크된 답안을 살펴보니 조금 배아픈 답안이 있었다.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let s = new Set(nums);
    return s.size!=nums.length;
};

 

Set() 활용해 만든 것 까지는 좋았는데. Object의 길이를 얻기 위해 굳이 다시 배열로 만들어 넣은 것이 패착.

 

그냥 Set()으로 만든 object는 size로, 주어진 Array nums는 length로 길이를 구하면  손쉽게 해결될 문제였다.