[LeetCode] 217. Contains Duplicate

문제

leetcode.com/problems/contains-duplicate/

Contains Duplicate - LeetCode

 

잠깐

단순 이중 for문으로 구현하면 안될것 같은 느낌 받으셨죠?

그럼 특정 작업 후 이중 for문으로 구현하거나 단일 for문으로 구현해야 할거 같은데요

 

코드

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var numSet = Set<Int>()
        
        for num in nums {
            if numSet.contains(num) {
                return true
            }
            numSet.insert(num)
        }        
        return false
    }
}

 

 

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

 

설명

set을 사용하는 방법과 sort를 사용하는 방법으로 구현했습니다.

우선 set을 사용한 방법을 소개할게요. 

https://docs.swift.org/swift-book/LanguageGuide/CollectionTypes.html#//apple_ref/doc/uid/TP40014097-CH8-ID484%EF%BB%BF

Collection Types — The Swift Programming Language (Swift 5.6)

Sets A set stores distinct values of the same type in a collection with no defined ordering. You can use a set instead of an array when the order of items isn’t important, or when you need to ensure that an item only appears once.

set은 중복을 허용하지 않는 집합이죠. 

또한, Swift 기준으로, set의 contains 시간 복잡도도 빅오(1)로 적절해 보입니다.

developer.apple.com/documentation/swift/set/1540013-contains

Apple Developer Documentation

그래서, 배열을 탐색하며 set에 존재하는지 확인하고, 존재하지 않으면 추가 하는 로직입니다.

물론, sorted 후 set에 추가하면 메모리 사용은 하겠지만, 더 빠르겠네요.

 

 

다음은, sort를 사용한 방법입니다.

developer.apple.com/documentation/swift/arra

Apple Developer Documentation

 

Apple Developer Documentation

Swift에는 sort()와 sorted()가 존재하는데 차이점은 array를 직접 정렬하는가와 정렬된 array를 return 해주는가 입니다.

매개변수는 let이므로 변경이 불가능하기 때문에 sorted()를 사용했습니다.

sorted()의 시간 복잡도는 "n로그n"으로 괜찮네요.

 

developer.apple.com/documentation/swift/array/2296815-sorted

Apple Developer Documentation

만약 array에 중복 값이 있다면, 정렬 후 나란히 배치가 될 것이고, 다음 엘리먼트만 비교하면 되겠죠.

 

사실 sort로 먼저 구현했지만, 종료 시점을 잘못구현하여 에러 발생으로 set 방법으로 구현해봤어요.

플레이 그라운드 개발은 좀 귀찮고, LeetCode에서 바로 개발 하다보니 디버깅이 좀 빡센 부분이 있네요