217. Contains Duplicate

2025-03-31
leetcode
LeetCode 217번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Contains Duplicate - LeetCode

풀이 1

아이디어

자주 사용했던 패턴이라 문제를 보자마자 바로 Set을 활용하기로 했다. nums에서 중복된 원소를 제거하기 위해 nums를 이용해서 중복을 허용하지 않는 자료구조인 Set을 생성한다. (numSet) 중복된 원소가 있었다면 numSet에서 제거되어 nums의 길이와 numSet의 크기가 다를 것이므로 비교해서 결과를 반환한다.

코드

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를 반환한다.

중복인 원소를 발견하자마자 순회를 멈추기 때문에 시간 복잡도는 동일하지만 아주 약간 더 빠르다…

코드

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