5/10 수 [LeetCode #217] 배열에 중복되는 값이 있으면 true 반환하기 TIL

[LeetCode] 217. Contains Duplicate

Contains Duplicate - LeetCode

Can you solve this real interview question? Contains Duplicate - Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.   Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true   Constraints: * 1 <= nums.length <= 105 * -109 <= nums[i] <= 109

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

문제:

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 105

• 109 <= nums[i] <= 109

나의 풀이:

// Map 이용해서 풀이
// time complexity: O(N)
// space complexity: O(N)
var mapSolution = function(nums) {
    const map = new Map();
    for (const num of nums) {
        if (map.has(num)) {
            return true;
        }
        map.set(num, true);
    }
    return false;
};

// Set을 이용해서 풀이
var setSolution = function(nums) {
    const set = new Set(nums);
    return set.size !== nums.length;
}

// 순수 Object을 이용해서 풀이
var objectSolution = function(nums) {
    const obj = {};
    for (const num of nums) {
        if (num in obj) return true;
        obj[num] = true;
    }
    return false;
}

• 세 방법 전부 시간과 공간 복잡도가 크게 차이 나지 않는다. 다만 순수 Object을 이용한 3번째 방법이 공간과 시간이 미세하게 더 적게 드는 것 같긴 하다.

순수 Object와 Map, Set 속도 비교 테스트 :

참고함: https://leetcode.com/problems/contains-duplicate/solutions/515531/javascript-set-vs-object/?orderBy=most_votes&languageTags=javascript

Node v18에서 실행함.

// 테스트용 timing 라이브러리
const { performance } = require('perf_hooks');

function runTest(testFunction, testArray) {
	console.log('	Running test:', testFunction.name);
	let start = performance.now();
	let result = testFunction(testArray);
	let end = performance.now();
	console.log('		Duration:', end - start);
}

// 각각 천 개, 만 개, 십만 개, 백만 개, 천만 개의 원소를 끝까지 확인하는(루프 도는) 경우의 시간을 측정함. 
const testSizeList = [1000, 10000, 100000, 1000000, 10000000]
for (const testSize of testSizeList) {
	let arr = [];
	for (let i = 0; i < testSize; i++) {
		arr.push(i);
	}
	
	console.log('Test size: ', testSize);
	runTest(mapSolution, arr);
	runTest(objectSolution, arr);
	runTest(setSolution, arr);
}

// => 결과: 
Test size:  1000
        Running test: mapSolution
                Duration: 0.4161999225616455
        Running test: objectSolution
                Duration: 0.45260000228881836
        Running test: setSolution
                Duration: 0.25259995460510254
Test size:  10000
        Running test: mapSolution
                Duration: 6.0817999839782715
        Running test: objectSolution
                Duration: 1.2177999019622803
        Running test: setSolution
                Duration: 0.7796000242233276
Test size:  100000
        Running test: mapSolution
                Duration: 15.777999997138977
        Running test: objectSolution
                Duration: 15.358699917793274
        Running test: setSolution
                Duration: 10.003900051116943
Test size:  1000000
        Running test: mapSolution
                Duration: 194.5887999534607
        Running test: objectSolution
                Duration: 35.73800003528595
        Running test: setSolution
                Duration: 123.77240002155304
Test size:  10000000
        Running test: mapSolution
                Duration: 4117.5463000535965
        Running test: objectSolution
                Duration: 349.27730000019073
        Running test: setSolution
                Duration: 3009.53100001812

결과 비교:

원소 1,000 개:

Map: 0.42ms

Object: 0.45ms

Set: 0.25ms

원소 10,000 개:

Map: 6.08ms

Object: 1.22ms

Set: 0.78ms

원소 100,000 개: 여기까지는 Set이 Map과 Object보다 더 빠르다.

Map: 15.78ms

Object: 15.36ms

Set: 10.00ms

원소 1,000,000 개: 여기서부터 Object가 가장 빠르다. Set보다 약 3.5배 빠르다.

Map: 194.59ms

Object: 35.74ms

Set: 123.78ms

원소 10,000,000 개: Object가 Set보다 약 8.6배 빠르다.

Map: 4117.55ms

Object: 349.28ms

Set: 3009.53ms

알게된 것:

• Map과 Set 등을 이용한 다른 해법(함수)의 속도를 측정하는 간단한 방법을 알게 되었다. perf_hooks 라이브러리의 performance.now()로 시작과 끝 시간을 찍어서 비교하면 된다.

• 크기가 백만 개를 넘으면 순수 Object가 Map보다 속도가 빠르다.

---

※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

Uploaded by N2T