LeetCode알고리즘 Contains Duplicate

중복 제거에 대한 알고리즘을 풀어보려 합니다.
중복을 제거하는 방법에 대해서 여러 가지가 존재해서 여러가지 방법을 사용해서 문제를 해결하겠습니다.

오늘 풀 문제는 217번이고 쉬운 난이도고 57%의 성공률을 보이네요.
그렇게 어렵지는 않은 문제인 것 같아요!

먼저 문제를 살펴보겠습니다.

정수형 배열 nums가 주어지고 값이 배열에 적어도 두 번 나타나면 참을 리턴하고 모든 숫자가 고유하다면 거짓을 반환합니다.
즉 중복되는 게 있으면 바로 참을 리턴해주면 됩니다.

1번 예시를 보면 1이 중복되니 참을 리턴해줍니다.
2번 예시를 보면 모든 숫자가 중복되지 않아서 거짓을 리턴해줍니다.
3번 예시를 보면 1이 중복되고 3이 중복되고 4가  중복되고 2가 중복되어 참을 리턴해줍니다.

생각나는 방법이 3가지 있었는데 아래와 같습니다. 

---

집합 사용하기

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        let set = Set(nums)
        return set.count < nums.count ? true : false
    }
}

집합의 특성을 사용해서 중복을 제거합니다.
집합 set에서는 유일한 숫자만 남게 됩니다.

1번 예를 그림으로 보자면 아래와 같습니다.

이 두 개의 개수로 중복의 여부를 판단합니다. 
nums를 집합화해서 중복된 숫자가 없으면, set의 개수와 nums의 수가 동일하고
nums를 집합화해서 중복된 숫자가 있으면, set의 개수가 nums의 수보다 작습니다.

이렇게 제출하면 아래와 같은 결과가 나옵니다.
count함수를 사용해 비교하기 때문에 시간 복잡도는 O(1)이 나오게 됩니다.

---

정렬 후 인접한 수 비교

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        let sortedArr = nums.sorted()
        
        for i in 0..<sortedArr.count-1 {
            if sortedArr[i] == sortedArr[i+1] {
                return true
            }
        }
        return false
    }
}

주어진 배열을 먼저 정렬해줍니다. (작은 것부터 큰 순서대로)
i와 i+1로 두어서 바로 오른쪽에 있는 숫자와 같은지를 비교해줍니다.
정렬했기 때문에 중복 여부를 확인하기 위해서는 바로 한 칸 뒤인 (i+1)만 확인해주면 됩니다.

이렇게 제출하면 결과는 아래와 같습니다.
sorted를 사용해서 O(nlogn) + for 루프 O(n)이 나와 총 시간 복잡도는 O(nlogn)이 나오게 됩니다.

---

딕셔너리 사용하기

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var dict = [Int: Int]()
        
        for i in nums {
            if dict[i] != nil {
                return true
            } else {
                dict.updateValue(1, forKey: i)
            }
        }
        return false
    }
}

딕셔너리에 key와 value를 설정해줍니다.
루프를 돌면서 각 숫자들을 dict에 넣어줍니다.
처음 딕셔너리에 숫자를 넣으면 해당 숫자에 대한 값이 없어서 nil이 리턴됩니다.
그리고 else부분을 실행하게 됩니다.

1번 예로 [1,2,3,1]을 딕셔너리에 넣는다고 생각해봅시다.
우선 1,2,3까지 넣으면 아래와 같은 그림이 됩니다.
(왼쪽이 key이고 오른쪽이 value입니다) 

여기서 1을 추가로 넣으려고 하면 이미 1을 key로 하는 value가 존재하기 때문에 nil이 아니게 됩니다.
그럴 때는 중복된 숫자니 참을 리턴해줍니다.

이렇게 제출하면 아래와 같은 결과가 나옵니다.
for 루프를 사용해 O(n)의 시간 복잡도를 가지게 됩니다.

 

resource: leetcode.com/problems/contains-duplicate/