[LeetCode] 217. Contains Duplicate with Swift 배열에서 반복되는 수 찾기

 

Contains Duplicate - LeetCode

217번 문제는

nums는 int형 숫자의 배열이고 이 배열에서 반복되는 값이 있을 때 true를 반환

그렇지 않은 경우 false를 반환하는 것입니다.

 

언뜻 보기에 배열의 모든 수를 탐색해야 할 것 같지만

그렇게 하면 시간 효율성 측면에서 낮은 점수를 받을 수 밖에 없습니다.

차근차근 배열에서 중복된 값을 찾기 위해서 어떤 알고리즘과 함수를 써야 할지 알아봅시다.

 

1. 순수한 선형 탐색

말 그대로 배열을 선형 탐색합니다. 각 원소를 하나씩 비교하며 같은 수를 찾으면 true를 반환합니다. 배열의 모든 원소 탐색을 끝낸 뒤 같은 수가 없다면 false를 반환하게 합니다. 이 알고리즘은 이중 for문이 사용되기 때문에 O(n^2)의 시간 복잡도를 가집니다. 😅

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        
        for i in 0..<nums.length {
            for j in 0..<i {
                if (nums[j] == nums[i]) {
                    return true
                }
            }
        }
        
        return false
    }
}

순수한 선형 탐색은 데이터 갯수가 많아질 수록 점점더 시간이 오래 걸릴 것입니다. 효율적인 다른 방법을 알아봐야 할 것 같습니다.

 

2. 정렬 알고리즘

배열의 sort()를 이용해서 배열을 정렬할 수 있습니다. 크기 순으로 정렬되기 때문에 반복되는 값을 찾으려면 자신의 앞이나 뒤에 있는 배열과 비교 하여 중복하는지 알아보면 됩니다. 이때 주의할 점은 배열 인덱스 범위가 벗어나지 않도록 주의 해야 합니다. heapsort를 사용할 경우 공간 복잡도는 O(1), sort()를 이용할 경우 복잡도는 O(n log n) 입니다. 

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

참고로 배열의 min()과 max()는 O(n)을 가집니다.

 

3. Set

set은 집합이라고 부르기도 하던데 이하 셋이라 부르겠습니다. 탐색과 삽입 정렬에서 해시 테이블과 이진 트리가 주로 사용됩니다. 이때 정렬되지 않은 배열에서 중복된 값을 찾기 위해 Hashtable을 이용하면 시간 복잡도를 줄일 수 있습니다. 스위프트에서 Set과 Dictionary는 Hashable을 상속 받고 있습니다. Set과 Dictionary는 중복을 허용하지 않기 때문에 중복되지 않도록 데이터를 저장할 수 있고 찾는 속도 또한 빠르다는 장점이 있습니다. 단, 순서가 없기 때문에 순차대로 읽어와야 하는 데이터를 저장할 때는 사용하지 않도록 주의 해야 합니다. 

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

contains()는 인자로 받은 값이 해당 셋에 있는지 확인합니다. O(n)이며 이보다 빠르게 하기 위해서는 count를 사용할 수 있습니다. count는 O(1) 입니다.

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        if nums.count == 1 { 
        	return false 
        }

		if nums.count != Set(nums).count {
			return true
		}
		return false
	}
}

Set으로 배열을 받으면 중복된 값을 허용하지 않기 때문에 중복된 값이 있는 배열과 갯수가 달라지게 됩니다. 

 

마지막으로. HashTable

해시 테이블은 value와 key를 가지는 데이터 구조체 입니다. 딕셔너리 연산은 보통 O(1)을 가지게 되는데 이는 상수 연산과 같은 시간 복잡도를 가지게 됩니다. 즉 데이터가 유연하게 증가하고 줄어든다고 해도 보통적으로 같은 시간의 연산 속도를 가지게 됩니다. 

이때 주의해야 하는 것은 해시 충돌입니다. 다른 값이 input되었지만 같은 hash 값을 가지는 경우를 말합니다. 그러나 같은 해시 값을 가지는 인스턴스가 같다는 뜻은 아닙니다! 해시 충돌은  하나의 key가 여러 값을 가지고 있다는 의미로 볼 수 있는데 이렇게 되면 고유의 값을 찾는 것에서 이점이 줄어들 수 있습니다. 즉 해시충돌이 빈번할 경우 시간 복잡도는 증가하게 됩니다.

이를 보완하기 위해 Swift에서는 hasher라는 것이 있습니다.

 

 

👉틀리거나 잘 못된 내용 지적 언제나 환영입니다~ 댓글 부탁드려요!