(Swift) Set 타입

Set

일련의 값들이 순서를 가지고 (혹은 그 순서는 별로 중요하게 아니더라도) 집합을 이루고 있을 때 사용하는 가장 흔한 자료 구조는 배열이다. 배열은 원소들이 연속적으로 저장된다는 점에 기반하여 임의 원소에 빠르게 액세스할 수 있는 점과 선형적인 구조에 기반한 여러 테크닉들을 적용할 수 있다는 점에서 널리 사용된다.

하지만 배열은 집합과 관련된 문제에 대해서 항상 옳은 선택이 아닐 수 있다. 예를 들어 특정한 값이 집합내에 포함되어 있는지 여부는 contains(_:)를 통해서 손쉽게 알 수 있지만, 해당 메소드의 시간 복잡도는 $ O_{(n)} $ 이다. 이외에 배열은 두 개 이상의 배열에 대해서 합집합은 원소의 중복을 감안한다면 비교적 쉽게 얻을 수 있으나, 교집합이나 차집합에 대해서는 별도의 로직을 만들어서 이를 구해야하고 이 때의 성능도 거의 항상 $O_{(n)}$일 수 밖에 없다. 즉 개별 원소의 저장소로의 배열보다 집합 자체를 다뤄야 하는 상황이라면 배열보다 더 어울리는 자료구조가 있는데, 그것이 바로 Set이다.

Set은 순서없는 원소들의 집합으로 특정 원소의 포함 여부를 효율적으로 확인할 수 있을 때 사용하며, 집합의 원소들의 순서는 상관없을 때 사용한다. 또한, 집합 내 모든 원소는 유일하며 중복되지 않는다. 중복없는 원소를 빠르게 확인하는 것은 해시의 특성으로, Set의 원소가 되려는 타입 역시 Hashable을 만족해야 하는데, Swift의 기본 타입들은 기본적으로 이를 만족한다.1

생성

Set은 기본적으로 좌변의 타입이 지정되었을 때 배열 리터럴로 만들 수 있다. 2

var someSet : Set<Int> = [3, 5, 1, 8, 9]

혹은 배열과 비슷하게 init(arrayLiteral:)이나 init(_:Sequence)를 이용하는 게 가능하다.

var someSet = Set<Int>(arrayLiteral: 4, 3, 2, 1 9)

배열은 기본적으로 원소의 순서가 없다. 하지만 Collection 프로토콜을 지원하므로 사실, Index만 알고 있으면 [i]문법으로 subscript하는 것이 가능하다. 3 대신에 Set에서 원소와 관련된 연산은 다음과 같은 것들이 주가 되겠다.

  1. 원소 추가 (insert(_:))
  2. 원소 제거 (remove(_:)) 4
  3. 원소가 있는지 검사 (contains(_:))
var s: Set<Int> = [1, 2, 3, 6, 9, 15]

s.insert(24)

if let r = s.remove(7) { print("removed 7") }
else { print("not found 7") }

if r.contains(9) { print("found 9") }
else { print("not found") }

집합 연산

사실 집합에서는 원소제어보다는 집합 간의 연산이 빛을 발한다. 이는 배열에서는 지원이 사실 좀 미미한 구석도 있고.

포함관계

두 집합 관계를 찾는다. 5

  1. 동치: ==로 비교한다.
  2. 포함관계: isSubset(of:), isSuperSet(of:)로 포함관계를 볼 수 있다.
  3. 엄격한 포함관계: isStrictSubset(of:), isStrictSuperset(of:)를 이용해서 완전히 포함되는지 여부를 볼 수 있다.
  4. isDisjoint(with:) 를 통해서 서로 소 집합인지를 볼 수 있다.

연산

다른 집합을 가져와서 교집합, 합집합, 차집합 및 서로 차집합을 구할 수 있다. 아래의 연산은 모두 새로운 사본을 만드는 것이며, mutating 메소드들은 아래에 다시 기술하겠다.

  • intersection(_:) 교집합
  • union(_:) 합집합
  • subtract(_:) 차집합
  • symmetricDifference(_:) 대칭차집합

원본을 변경하여 연산하는 메소드는 다음과 같다.

  • formUnion(_:)
  • formIntersection(_:)
  • subtracting(_:)
  • formSymmetricDifference(_:)
var odds = [1, 3, 5, 7, 9]
var primes = [2, 3, 5, 7, 11]

let u = odds.union(primes) // [1,2,3,5,7,9,11]
let i = odds.intersection(primes) // [3, 5, 7, 9]
let s = odds.subtract(primes) // [1]
let d = odds.formSymmetricDifference(primes) // [1, 11]

그외의 연산

그외의 연산에는 Set 타입이 콜렉션이자 시퀀스임을 기억하면 for in 순회라던지 맵/필터/리듀스를 적용할 수 있는 등의 기능을 지원한다는 것 정도는 알 수 있을 것 같다. 6

let doubleedPrime = primes.map{ $0 * 2 }
// [4, 6, 10, 14, 22]

브릿징

Swift의 Set 이전에 Objective-C 에서는 파운데이션에서 정의한 NSSet 클래스가 있었고, 이 두가지 타입은 브릿징이 되기 때문에 상호간에 바꿔서 쓰는 것이 가능하다. 다만 집합은 1차 타입이 아닌 원소의 타입에 의존하는 2차 타입이기 때문에 다음과 같은 조건을 만족해야 한다. (그리고 이 조건은 Array - NSArray, Dictionary - NSDictionary간의 브릿징에서도 동일하게 적용된다.)

  1. SetElement 타입이 클래스이거나
  2. Element 타입이 @objc 지시어에 의해 Objective-C에 노출되게끔 선언되어 있거나
  3. 혹은 파운데이션으로 브릿징되는 타입이어야 한다.

브릿징이 적용될 때 Swift → Objective-C 인 경우에 위의 조건 중 1 혹은 2에 해당하는 경우에는 항상 $O_{(1)}$의 시간/공간 복잡도를 가진다. 3의 경우에는 내부 원소 각각이 브릿징되는 작업이 추가로 필요하므로 $O_{(n)}$ 복잡도를 갖는다.

반대로 Objective-C → Swift의 경우에는 NSSet이 상수집합으로 넘겨지는 경우에는 상수시간이 소요되지만, mutable한 집합이 되는 경우에는 복사가 일어나야 하며, 이 경우의 시간 복잡도는 정의되지 않았다.


  1. Apple Developer – Set 
  2. 배열 리터럴이 Array가 될지 Set이 될지는 좌변의 타입에 의해 결정되므로 좌변에 반드시 변수의 타입을 명시하거나 as를 사용해서 캐스팅해야 한다. 
  3. 해시값에 의해서 각 원소가 저장되는 위치가 정해지므로 subscription은 가능하고 이를 위해서 Index 타입은 필요하지만, 집합내의 각 원소의 위치는 직관적이지는 않으므로 굳이 이게 필요하겠냐 만은… 
  4. remove(_:)는 제거한 원소를 리턴하며, 찾는 원소가 없으면 nil을 리턴한다. 따라서 해당 메소드의 리턴은 Element? 타입이다. 
  5. 동치관계 연산을 제외하면 Set외에도 Sequence에 대해서도 연산할 수 있다. 
  6. 물론 원래 타입이 Set이라 하더라도 Sequence의 맵필터리듀스는 늘 그 리턴타입이 [T] 즉, Array 타입이라는 점은 잊지 말자.