> [!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로 추가하는 것에서 발생하는 최적화 차이가 아닐까…