[LeetCode 해석 및 풀이] 217. Contains Duplicate

LeetCode 문제 해석 및 풀이 방법

 

문제 217. 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.

 

한글

정수 배열이 주어졌을 때, 값이 2번 이상 나타나면 true, 모든 요소가 다르면 false를 반환하세요.

 

제한조건

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

 

입출력 예

입력	출력
[1,2,3,1]	true
[1,2,3,4]	false
[1,1,1,3,3,4,3,2,4,2]	true

 

 

해답 및 해설

파이썬 (Python)

파이썬의 내장 함수들을 이용할 수도 있었겠지만, neetcode 로드맵에서 Array&Hashing이라 표시되어있어 Set 자료형을 이용해주었다.

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

 

파이썬의 set은 해쉬 테이블을 이용한 자료형이다. 이를 이용해 리스트를 set에 넣으면 중복된 값이 있다면 제거해줄 수 있고, 넣기 전과 후가 길이가 같은지 다른지에 따라 중복된 값이 있는지를 확인할 수 있다.

 

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

시간 복잡도는 위나 아래나 똑같이 O(n)이지만, 아래 코드는 겹치는 값이 발견되자마자 바로 나오기 때문에 조금 더 빠를수도 있다.