Software Development/Leetcode

Leetcode 217. Contains Duplicate

El스토리 2023. 1. 11. 15:25
반응형

217. 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
  • 이 문제는 nums 배열 하나를 parameter 로 받아 해당 배열에 중복된 값이 있는지를 판별하는 함수를 구현하는 것입니다.
  • map이라는 오브젝트를 생성한 후 nums 배열을 순회하면서 해당 element를 key값으로 지정하면서, value는 true로 지정합니다.
  • 지정하기 직전 map[num] 의 value 가 true 인지 확인을 하고 만약 true 면 바로 true를 리턴하는 방식으로 문제를 풀었습니다.

먼저 Map을 사용하여 풀어보겠습니다.

 

/*
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
*/

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const map = {};
    for(const num of nums) {
        if (map[num]) return true;
        map[num] = true;
    }
    return false;
};

Example 1 의 경우입니다.

Key Value
1 true
2 true
3 true
1 이미 true이기 때문에 Duplicate, 따라서 return true

 

4번째 for loop 순회시 이미 밸류 값이 true로 지정된 Key 1 의 경우 if (map[num]) 이 true 가 되면서 return true가 됩니다.

 

예제 2, 3은 생략하겠습니다. 

Node 로 예시 테스트를 해봤습니다.

 

true, false, true 로 잘 출력이 되는 것을 확인했습니다.

 

 

디버그 모드로 map 오브젝트의 변화에 대해 관찰해 봤습니다.

처음 배열 [1, 2, 3, 1] 의 경우에는 for 루프를 순회할 때 네번 째 element '1' 에서 map[num] 이 true를 반환하여  함수가 true 를 리턴하는지 확인 해 보겠습니다. 

 

리턴에 걸려서 함수를 나가지는 모습입니다.

 

 

 

 

이번에는 Map오브젝트 대신 Set을 사용해 보겠습니다.

 

배열의 인자들을 모은 집합을 Set으로 설정한 후 Set의 사이즈와 인자로 받은 배열의 길이를 비교하여 같지 않다면 (Set으로 생성된 인스턴스의 사이즈가 줄어듦) 중복된 값이 있는 것으로 보아 true를 리턴합니다.

var containsDuplicate = function (nums) {
	const set = new Set([...nums]);
	return set.size != nums.length;
};

 

예제 1의 경우 nums.length는 4, set.size는 3으로 동일하지 않으므로 true를 리턴하게 됩니다.

예제 2의 경우 둘다 4로 동일하므로 false를 리턴하게 됩니다.

 

Set([...num]) 는 num 배열의 인자 하나하나를 Set으로 만들어주는 부분입니다.

 

만약 Set([num]) 으로 설정하게 되면 set.size 가 항상 1이 되면서(num배열 전체가 하나의 set element가 됨) 인자 배열의 길이가 1이 아닌 이상에는 항상 true를 리턴하게 됩니다.

 

Map 을 사용한 방식과 Set을 사용한 방식의 성능에는 크게 차이가 없는 것으로 보입니다.

 

Visual Studio Code 에 Debug 모드를 활용해 elements 를 확인해 가면서 코드가 정상적으로 잘 동작하는 것을 확인해 보았습니다.

릿코드 스터디는 여기 티스토리 블로그에 앞으로도 꾸준히 올릴 예정입니다.

인터뷰 준비에 도움이 많이 되었으면 좋겠습니다.

 

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

 

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.

 

반응형