[DSA][Array & Hashing] 01. Contains Duplicate

LeetCode 217

 

01. 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.

 

 

[질문하기]

- 입력 배열의 길이 제한은 어떻게 되나요? 1 <= nums.length <= 10^5

- 숫자의 범위는 어떻게 되나요? -10^9 <= nums[i] <= 10^9

- 입력 배열이 정렬되어 있나요? NO

- 빈 배열이 입력으로 올 수 있나요? 만약 그렇다면, false를 return 해야 하나요? YES

- 모든 요소가 대부분 유일한가요? 중복이 많은가요? → 시간 복잡도를 우선할 것인지 공간 복잡도를 우선할 것인지 선택 가능

 

 

[아이디어]

특정 원소의 존재 여부를 빠르게 확인할 수 있는 자료구조는? set, hash

 

 

[풀이 1] set

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        numSet = set()
        for num in nums:
            if num in numSet:
                return True
            numSet.add(num)
        return False

set, hash 등이 원소 탐색에 O(1)의 시간 복잡도를 보이기 때문에, 시간 복잡도를 줄이기 위해 위의 방식으로 문제를 풀 수 있다.

또, 원소에 중복이 많다면 Early Exit이 가능하므로 유리하다.

 

⏱️ 시간복잡도

nums 리스트의 모든 원소를 한 번씩 순회하고, set 자료구조의 경우 탐색에 걸리는 시간 복잡도가 O(1)이므로 전체 시간 복잡도는 O(n)이다.

 

🧠 공간복잡도

최악의 경우 nums 리스트의 모든 원소를 저장해야 하기 때문에 공간복잡도는 O(n)이다.

 

 

[풀이 2] sort

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

공간 복잡도가 우선일 경우, 혹은 in-place로 문제를 풀이해야 할 경우는 정렬 O(nlogn) 후에 인접 비교 방식을 사용할 수 있다.

또, 원소가 대부분 유일하다면, Full Scan을 해야 하므로 공간에 제약이 있는 경우 유리하다.

 

⏱️ 시간복잡도

정렬을 하기 때문에 시간 복잡도는 O(nlogn)이다.

🧠 공간복잡도

Python의 sort()의 경우 in-place 정렬인 Timsort를 사용하기 때문에 공간복잡도는 O(1)이다.

※ sorted()의 경우 새 리스트를 만들어 반환하기 때문에 O(n)이 필요하다.