[LeetCode] 217. Contains Duplicate

목표없이 풀다보니 의지가 약해지는 것 같아 'data structure'로 묶인 문제를 풀기로 결정.

https://leetcode.com/study-plan/data-structure/?progress=x0f8sqb1 

Data Structure - Study Plan - LeetCode

 

 그 중 1일차 Array 문제

https://leetcode.com/problems/contains-duplicate/?envType=study-plan&id=data-structure-i

Contains Duplicate - LeetCode

 

중복 숫자가 있으면 true, 없으면 false 아주 쉬운 문제다.

이런건 역시 hashtable로 푸는게 최적일 것 같다.

 

파이썬 풀이1

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        table = {nums[0]}
        for n in nums[1:]:
            if n in table:
                return True
            table.add(n)
        return False

시간복잡도는 O(N)에 iteration도 중간에 끝나는 괜찮은 코드인 것 같다.

 

파이썬 풀이2

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

진짜 naive하게 짠 코드지만 의외로 이 코드는 메모리는 많이 먹어도 속도가 빠르다.

 

 

아무래도 매번 이터레이션을 도는 것 보다 set을 하나 새로 만들고

2개의 object의 길이를 built-in property에서 가져오는 것이 더 빠른 것 같다.

의외로 이게 pythonic한 코드일지도...?

 

코드 인터뷰에서는 1번처럼 작성하고

실무에서는 2번처럼 작성할 것 같다.