Leet code 217 - Contains Duplicate

 

 

파이썬 내부함수인 set을 통해 자료형 변환을 하고, 중복제거해 중복제거한것과 길이가 다르다면 duplicate가 있다고 판단, True를 반환했다. 아니면 그대로 false. 

매우 간단하게 풀렸지만, 학습의 본질과 맞지 않은 것 같아. 다른 풀이도 공부해보기로 했다.

 

나의 풀이

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(set(nums)) != len(nums):
            return True

        
        return False

---

문득 내가쓴 함수의 시간복잡도가 궁금해졌다.

 

파이썬 함수의 시간복잡도.

len 함수는 O(1)의 시간 복잡도를 가지고 있다고 한다.

 

len함 수가 실행되면 __len__()라는 내부 메소드를 실행하게 되는데,

이미 순회가능한 데이터 구조들에 미리 저장되어 있는 메소드이다. 이 메소드는 카운터의 역할을 하며 순회할 필요 없이, 자료구조가 선언되고 저장되는 순간부터 자동적으로 1씩 증가해 길이를 저장하게 된다.

def length(ar):
   
    # calling the internally 
    # defined __len__() method
    return ar.__len__() 
  
# Driver code
a = [1, 2, 3, 4]
print(length(a))

따라서 O(1)의 시간복잡도를 지닌다.

https://www.geeksforgeeks.org/internal-working-of-the-len-function-in-python/

 

list,와 set 함수는 선언하는 리스트와 set 의 길이에 비례한다고 한다.

다만 list(set(nums)에서 시간 복잡도가 O(N^2)이 되지는 않는 듯.

---

1. Brute force

def containsDuplicate(self, nums: List[int]) -> bool:
    n = len(nums)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if nums[i] == nums[j]: return True
    return False

 

리스트를 전부 하나씩 순회하며 중복이 있는지 확인하는 코드.

시간초과 발생.

 

2. Sorting

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

정렬하고, 앞뒤 인덱스에 해당하는 값을 비교해 계산. 시간초과가 발생하지는 안흔다.

 

3.카운터함수 사용.

def containsDuplicate(self, nums: List[int]) -> bool:
    freq = Counter(nums)
    for num, freq in freq.items():
        if freq > 1:
            return True
    return False

카운터는 dict의 서브 클래스로, 해싱가능한 객체를  세기 위한 함수이다.

해당 요소가 몇개가 등장하는지 세서 해시로 반환한다.

거기서 숫자 2이상이 나온다면 True 반환.

 

4. 딕셔너리 사용

 

앞의 카운터 함수 모방

def containsDuplicate(self, nums: List[int]) -> bool:
    counter = {}
    for num in nums:
        if num not in counter:
            counter[num] = 0
        counter[num] += 1
    for num, freq in counter.items():
        if freq > 1:
            return True
    return False