217. Contains Duplicate

1. Description

• 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. Example

Example 1

Input: nums = [1,2,3,1] Output: true Explanation: The element 1 occurs at the indices 0 and 3.

Example 2

Input: nums = [1,2,3,4] Output: false Explanation: All elements are distinct.

3. Solution

1. 첫번째 풀이
   • Runtime: 49ms
   • 설명
     • 이 방법은 내 친구(Seong)가 생각한 방법이다.
     • List를 정렬을 한다.
     • List의 첫번째 index를 i로 칭하고 i와 i+1번째 List value를 비교한다.
     • 이를 range(len(list)-1)만큼 for문을 돌린다.
     • i와 i+1번째 List value가 같다면 return True, 다르면 return False를 나타낸다.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        new = sorted(nums)
        #nums.sort()
        i = 0
        
        for num in range(len(new)-1):
            if new[i] == new[i+1]:
                return True
            else: 
                i = i+1
        return False

• 📌런타임을 줄여서 조금 더 효율적인 방법을 찾고자 하여 다른 사람의 코드를 확인해 보았다.

2. 두번째 풀이
   • Runtime: 8ms
   • 설명
     • 빈 Set s를 정의한다.
     • for문으로 nums리스트가 돌아갈 때, n이 빈 Set인 s안에 있다면 return True
     • s안에 없다면 s에 n을 추가한다.
     • for문을 다돌렸을 때에도 s집합안에 value와 같은 value가 없다면 return False

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

두번째 풀이에서 list대신에 set를 쓴 이유

• List
  • 리스트는 순차적으로 데이터를 저장하는 구조이다.
  • 원소가 리스트에 있는지 확인하려면, 처음부터 끝까지 순차적으로 탐색해야한다.
  • 최악의 경우, 모든 원소를 비교해야 하므로 O(n) 시간이 걸린다.
    • 원소가 많아질수록 탐색 시간이 길어지는 선형 탐색(linear search)방식이기 때문이다.
• Set
  • 집합은 해시 테이블(Hash Table)을 기반으로 동작한다.
  • 해시 테이블은 원소를 고유한 해시 값(Hash Value)으로 변환하여 저장한다.
  • 원소가 존재하는지 확인할 때, 해시 값을 이용하여 바로 해당 원소의 위치를 찾을 수 있으므로 O(1) 시간에 처리가 가능하다.
• Hash Table
  • 키-값(key-value) 구조로 데이터를 저장하는 자료구조이다.
  • Python의 set는 내부적으로 딕셔너리(dict)와 같은 해시 테이블 구조를 사용한다.
  • 해시 테이블 원리
    1. 원소 n을 저장할 때, hash(n)을 계산하여 특정 메모리 위치(버킷)을 찾음
    2. 해당 위치에 저장
    3. n이 존재하는지 확인할 때도 같은 hash(n)을 이용하여 즉시 확인 가능
• 📌set는 내부적으로 해시 테이블을 사용하기 때문에 원소가 존재하는지 확인하는 연산이 평균적으로 O(1) 시간에 수행된다.
  • n개의 원소를 검사할 때 전채 수행 시간은 $O(n)$이다.
• 📌list는 if n in s부분이 리스트에서 특정 값이 존재하는지 확인하는 연산인데, 리스트에서는 O(n) 시간이 걸린다.
  • 이 연산이 리스트의 모든 원소에 대해 실행되므로, 최악의 경우 $O(n^2)$ 시간이 소요된다.

3. 세번째 풀이
   • Runtime: 0ms
   • 설명
     • nums의 list 길이와 set의 길이가 다르면 return True 같으면 return False

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

• 📌set와 list의 성질을 이용해서 이런 식으로 풀이하는 방법이 있다는 것을 알면 좋을 거 같다.

4. What I Learned

References

Chat GPT