[Top Interview Questions] 217. Contains Duplicate

정답)

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

        for n in nums:
            if n in dupSet:
                return True
            else:
                dupSet.add(n)
        
        return False

문제)

문제출처

 

정수 배열 nums가 주어졌을 때, 배열의 어떤 원소가 적어도 두 번 존재한다면 True를 리턴하시오.

만약 모든 원소가 한 번씩밖에 존재하지 않는다면 False를 리턴하시오.

 

예시 1)

nums = [1, 2, 3, 1]

output = True

 

예시 2)

nums = [1, 2, 3, 4]

output = False

 

예시 1)

nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

output = True

 

제한)

1 <= nums.length <= 100000

-1000000000 <= nums[i] <= 1000000000

풀이)

이런 문제를 가장 쉽게 접근하는 방법은 메모리를 활용하는 방법입니다.

 

nums 배열을 선형하면서 따로 저장공간에 nums의 숫자들을 저장해 주고 전에 등장한 적 있는지 확인하는 방법으로 숫자가 적어도 두 번 존재하는지 확인하는 방법이겠죠.

 

이렇게 할 경우 시간 복잡도와 공간 복잡도 모두 O(n)이 됩니다. 왜냐하면 nums가 [1, 2, 3, 4]와 같은 경우 nums의 len인 n만큼 선형하고 n만큼 저장해야 되기 때문이죠.

 

하지만 문제에서 따로 공간 복잡도의 제약은 없다고 했으니 위와 같은 방식으로 문제를 풀어주겠습니다.

 

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
    	dupSet라는 세트 변수

        nums를 선형하는동안:
            nums의 숫자가 dupSet에 존재하면 True를 리턴
            
            dupSet에 존재하지 않는다면 dupSet에 추가 
        
        False를 리턴

세트 변수)

저장공간으로 저희는 세트를 사용할 것입니다.

전에도 말했듯이 어떤 원소가 세트에 존재하는지 확인할 때 시간복잡도가 O(1)로 굉장히 효율적이기 때문입니다.

 

그러므로 세트 변수 dupSet을 만들어줍시다.

 

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

nums를 선형)

세트 변수를 만들어줬다면 이제 nums를 선형 합니다. nums의 원소가 dupSet에 존재하지 않는다면 dupSet에 추가해줄 것입니다. 하지만 어떤 원소가 dupSet에 존재한다면 그 원소는 nums안에 적어도 두 번 존재한다는 뜻이 됩니다.

 

예를 들어 nums가 [1,1]이라면 0번째 1은 dupSet에 추가될것입니다.

하지만 1번째 1은 dupSet에 이미 1이 존재하는 것을 확인했기 때문에 바로 True를 리턴해 nums 안에 2번 존재한다는 것을 알려줍니다. 

 

nums = [1, 1]

nums의 선형이 완료됐다면 nums의 원소들이 전부 한 번만 존재하는 원소들이라는 뜻이므로 False를 리턴합니다.

 

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

        for n in nums:
            if n in dupSet:
                return True
            else:
                dupSet.add(n)
        
        return False

디버깅)

nums = [1, 2, 3, 1]

dupSet = ()

 

(n = 1)

dupSet = (1)

 

(n = 2)

dupSet = (1, 2)

 

(n = 3)

dupSet = (1, 2, 3)

 

(n = 1)

return True

 

 

오랜만입니다! 오늘 문제는 나름 간단했던 것 같습니다. 공간 복잡도의 제약이 있었다면 상당히 어려웠겠지만 그런 것도 아니었기 때문에 간단히 세트를 이용하여 문제를 풀어줬습니다. 일주일 동안 쉬다 와서 못 풀까 봐 걱정했는데 쉬운 문제가 나와서 다행이네요 ㅎㅎ

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)