[Leetcode] 217. Contains Duplicate_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '217. Contains Duplicate'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Contains Duplicate' 알고리즘 문제

 

STEP 2. 'Contains Duplicate' 코드(code)

 

STEP 3. 'Contains Duplicate' 해설

 

STEP 4. 'Contains Duplicate' solution

 

반응형

 

STEP 1. '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.

 

정수 배열 nums가 주어지면 값이 배열에 두 번 이상 나타나면 true를 반환하고 모든 요소가 고유하면 false를 반환합니다.

 

Constraints:

1. 1 <= nums.length <= 105

2. -109 <= nums[i] <= 109

 

---

STEP 2. 'Contains Duplicate' 코드(code)

 

■ Runtime: 412 ms Beats 73.62% of users with Python3
■ Memory: 31.92 MB Beats 65.41% of users with Python3

 

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

---

STEP 3. 'Contains Duplicate' 해설

 

array에서 고유한 값만 가져야 하기에, set 함수를 적용하여 고유한 집합을 계산하고 이를 원본 nums와의 길이가 다를 경우에는 True, 같은 경우는 False를 판단하도록 계산했습니다.

 

 

STEP 4. 'Contains Duplicate' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

Hash set를 적용하여, memory complexity를 O(n)으로 줄인 방법입니다.

 

해당 방법은 nums를 확인하면서, set에 없는 경우에 set에 추가하고, 있는 경우는 중복값 (duplicate)이 존재하기에 True를 반환합니다. 만약 모든 nums를 검토해도 중복값이 없으면, 모두 고유하기에 False를 반환합니다.

 

■ Runtime: 404 ms Beats 91.47% of users with Python3
■ Memory: 31.87 MB Beats 86.55% of users with Python3

 

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        num_set = set()

        for n in nums:
            if n in num_set:
                return True
            else :
                num_set.add(n)
        return False

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '217. Contains Duplicate'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.