Leetcode) Contains Duplicate

Top Interview Questions
Easy Collection

Link of Problem

LEVEL : 🌕 🌑 🌑 🌑 🌑 (최하)

---

Easy Collection의 네번째 문제인 Contains Duplicate를 풀어봤습니다.

첫번째 문제에서는 중복을 제거했다면 이번 문제는 중복이 있는지 확인하는 문제였습니다.

전에 한 번 중복을 찾아내는 문제를 풀었기 때문에 그와 비슷한 방식으로 문제를 풀어나갔습니다.

1️⃣ 번째 방법

첫번째 방법은 시간 초과가 난 로직입니다.

저번에도 시간 초과가 났었는데, 이번 문제에서도 시간 초과가 발생했습니다.

가장 기본적인 이중 for문으로 짰었기에, 짤 때부터 이건 시간 초과가 발생하겠구나 싶은 로직이었습니다.

문제가 생긴 이유
1<= element 갯수 <= 10^5 만큼의 배열크기가 들어올 수 있다고 했기 때문에 숫자가 커짐에 따라 시간 초과 문제가 발생한 것 같습니다. 이미 문제를 풀면서도 예상했던 부분이었습니다.

func containsDuplicate(_ nums: [Int]) -> Bool {
    guard nums.count > 1 else { return false }
    
    for i in 0..<nums.count-1 {
        for j in i+1..<nums.count {
            if nums[i] == nums[j]{
                return true
            }
        }
    }
    return false
}

2️⃣ 번째 방법

서로 멀리 떨어진 숫자들을 어떻게 대조해서 중복이 있는 걸 찾을까 고민을 하다가,
멀리 떨어져있다면 붙이면 되겠다 라는 생각이 들었습니다.

일단 정렬을 하고 나서 양 옆에 같은 숫자가 있는지 확인하는거죠.

func containsDuplicate(_ nums: [Int]) -> Bool {
    guard nums.count > 1 else { return false }
    
    let num = nums.sorted()
    
    for index in 1..<nums.count {
        if num[index] == num[index-1]{
            return true
        }
    }
    return false
}

nums가 전 문제들처럼 inout으로 써진게 아니여서 따로 num이라는 배열을 사용했습니다.

그리고 num에 있는 element들 양옆에 같은 숫자가 있으면 true를 바로 return하도록 로직을 짰습니다.

2번째 방식의 Runtime은 중간정도의 속도가 나오더군요.

3️⃣ 번째 방법

3번째 방법은 보자마자 왜 나는 이런 생각을 못했을까 싶었던 방식이었습니다.

바로 중복을 싫어하는 Set를 써서 Set에 들어간 nums의 갯수와 그냥 nums의 갯수를 비교하는거죠.
만약 중복이 있다면 Set에 들어간 것과 그냥 nums에 있는 원소의 갯수가 차이날 것입니다.

func containsDuplicate(_ nums: [Int]) -> Bool {
    nums.count != Set(nums).count
}

고작 한 줄 입니다. 왜 이 생각을 못했을까요?
항상 중복이 나오면 Set를 쓰자라고 생각을 했는데, 이번 문제에서는 왜 그러지 못했는지..🥲

알고리즘 더 열심히 해야겠습니다.