217. Contains Duplicate (Easy) [Python]

문제

생각 방식

Empty 리스트를 하나 만들어서 그 안에 혹시 중복된 value가 있는지 확인하고, 있으면 True, 없다면 False로 하면 될 것 같다.

 

💻 코드

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

 

 

Time Complexity: O(n^2)

시간 복잡도가 높기에 다른 해결 방안을 생각해 보았다

 

다른 방법은 set()을 사용하는 것이다.

"In Python, sets have an algorithmic complexity of O(1) for average case time complexity for common operations like adding, removing, and checking for membership."

그래서 이런 케이스에서 loop을 사용한다면 O(n)이 된다.

 

💻 코드

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

        for num in nums:
            if num in s:
                return True
            s.add(num)
        return False

 

이 글을 작성하면서 좀 더 간결한 코드를 찾았다

(https://velog.io/@datawhales/Problem-Solving-with-Python-LeetCode-217.-Contains-Duplicate)

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

 

 

결과