Leetcode 217. Contains Duplicate

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 로 올릴 예정입니다.

 

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