> [!date] published: 2025-03-31 ## 문제 [Contains Duplicate - LeetCode](https://leetcode.com/problems/contains-duplicate/) `nums` 배열에 중복으로 등장하는 원소가 있다면 `true`, 아니면 `false`를 반환하는 문제 ## 풀이 1 ### 아이디어 자주 사용했던 패턴이라 문제를 보자마자 바로 Set을 활용하기로 했다. `nums`에서 중복된 원소를 제거하기 위해 `nums`를 이용해서 중복을 허용하지 않는 자료구조인 Set을 생성한다. (`numSet`) 중복된 원소가 있었다면 numSet에서 제거되어 nums의 길이와 numSet의 크기가 다를 것이므로 비교해서 결과를 반환한다. ### 코드 ```typescript function containsDuplicate1(nums: number[]): boolean { const numsSet = new Set<number>(nums); return numsSet.size !== nums.length; } ``` ### 시간 / 공간 복잡도 nums 배열을 이용해서 Set을 만드는 곳에서 **시간복잡도**는 **O(n)**이 된다. nums에 중복된 원소가 없는 최악의 경우 numSet을 생성하기 위해 n만큼의 공간이 추가로 필요하기 때문에 **공간복잡도**는 **O(n)**이 된다. ## 풀이 2 ### 아이디어 최악의 경우(모든 원소들이 중복이 아닌 경우)가 아닐 때 약간 더 빠르게 결과를 반환할 수 있는 방법 동일하게 Set을 활용하지만 직접 nums를 순회하며 numSet에 없는 원소일 경우에만 numSet에 원소를 추가한다. numSet에 이미 존재하는 원소를 nums에서 마주친다면 이 원소는 중복이므로 바로 true를 반환한다. 중복인 원소를 발견하자마자 순회를 멈추기 때문에 시간 복잡도는 동일하지만 아주 약간 더 빠르다… ### 코드 ```typescript function containsDuplicate2(nums: number[]): boolean { const numSet = new Set<number>(); for (let num of nums) { if (numSet.has(num)) { return true; } numSet.add(num); } return false; } ``` ### 시간 / 공간 복잡도 nums를 순회하며 Set을 만드는 곳에서 **시간복잡도**는 **O(n)** 이 된다. **공간 복잡도**는 풀이 2와 동일하지만 메모리가 2MB 이상으로 꽤 차이난다. 아마도 Set에 원소를 추가할 때 생성자로 추가하는 것과 add로 추가하는 것에서 발생하는 최적화 차이가 아닐까…