[leetcode] 217. Contains Duplicate 파이썬 코드

#arrays #hashing

 

리스트가 주어지고, 이 리스트 안에 있는 정수들이 중복되면 True를, 중복이 없으면 False를 리턴하는 문제다.

 

파이썬 dictionary를 활용했는데 파이썬 딕셔너리는 해시테이블/해시 맵에 해당되는 자료구조다.

 

 

def containsDuplicate(nums):
    val_dict = dict()
    for num in nums:
        if num in val_dict.keys():
            return True
        else:
            val_dict[num] = 1
    return False

print(containsDuplicate(nums))

 

이렇게 하니까 시간 초과가 났다.

val_dict.keys()를 하면, 가상의 view object를 만들고 여기서 비교하기 때문에 비효율적이다.

그 값이 딕셔너리에 있는지 없는지를 체크하고 싶다면, 그냥 val_dict를 쓰는 게 효율적이다.

view object를 만들지 않고 딕셔너리에서 바로 확인하기 때문이다.

 

def containsDuplicate(nums):
    val_dict = dict()
    for num in nums:
        if num in val_dict:
            return True
        else:
            val_dict[num] = 1
    return False

print(containsDuplicate(nums))

 

 

이 코드의 time complexity는 O(n)이다.

`if num in val_dict`이 O(1)이고, for loop을 돌면서 O(1 * n) => O(n)이 된다.

O(1)인 이유는 파이썬 딕셔너리가 hash table (hash map)으로 구현되어져 있기 때문이다.