[Swift] Collection Type - 집합(Set), 집합 연산, 반복, 정렬

안녕하세요! 이번 포스팅은 Swift 데이터구조와 알고리즘 책의 2장 스터디 중 두번째 핵심 내용인 Collection Type 에 대한 내용입니다. Array (배열), Dictionary (딕셔너리, 사전형), Set (집합), Tuple(튜플) 네가지 타입에 대해 학습했습니다.

---

🍡 집합(Set)

Set 은 서로 중복되지 않고, nil 이 포함되지 않은 순서가 없는 컬렉션입니다. Set 는 수학에서의 집합의 개념을 기반으로 만든 데이터 타입이라고 합니다. Set 의 데이터는 Dictionary의 Key 와 마찬가지로 Hashable 프로토콜을 부합해야 합니다! 기본 데이터 타입 외에 커스텀 타입도 지정할 수 있지만, 이 경우 Hashable 프로토콜을 부합하도록 만들어야 합니다. 

 

Set 은 배열보다 효율적이고, 데이터 접근 속도가 빠르다고 합니다. Hashable 프로토콜을 준수하기 때문이 아닐까요? 😶!! 배열의 크기가 n 일 때, 배열 요소 검색 시 최악의 시간복잡도는 O(n) 이지만 Set 의 경우 크기에 상관없이 O(1) 을 유지한다고 합니다. 그러므로 배열에서 요소의 순서가 중요하지 않고, 한 번만 나타나도 되는 경우, Array 대신 Set 을 이용하는 것이 효율적입니다!

 

✔︎ Set 초기화

• 비어있는 Set 초기화 시, 배열과 혼동되지 않기 위해 축약형을 제공하지 않는다고 합니다! Set 타입임을 명시해야 합니다.
• 배열 요소로 Set 초기화 시, Set 의 요소 타입을 생략할 수 있습니다.

// Creates an empty set
var stringSet = Set<String>()

// Creating a Set with an Array Literal
var stringSet1: Set<String> = ["A", "B", "C"]
var stringSet2: Set = ["A", "B", "C"]

 

✔︎ Set 요소 추가, 요소가 있는지 확인

• insert(_:) 메소드로 새로운 요소를 추가할 수 있다. 
  
  
  • 메소드 반환값은 (inserted, memberAfterInsert) 
  • inserted :: Set 에 새로운 요소가 추가되었는지에 대한 Bool 타입 - true / false
  • memberAfterInsert :: 추가하려는 값. 새로 추가된 경우 새롭게 추가된 값 / 추가되지 않았다면 기존 값
    
    
• contains(_:) 메소드로 특정 요소가 Set 에 포함되어있는지 알 수 있다. 반환값은 Bool 타입

stringSet.insert("A")
// (inserted: true, memberAfterInsert: "A")

stringSet.insert("A")
// (inserted: false, memberAfterInsert: "A")

stringSet.contains("B")
// false

 

✔︎ Set 요소 삭제

• remove(_:) 메소드는 특정 요소를 삭제한다.
  
  
  • 특정 요소의 값을 미리 알고 있어야 한다.
  • 특정 요소가 있다면 그 값을 리턴, 없다면 nil 을 리턴한다.
    
    
• remove(at:) 메소드는 특정 인덱스의 요소를 삭제한다.
  
  
  • 이때 인덱스는 배열에서의 Int 가 아닌 Set.Index 값이다.
  • firstIndex(of:) 메소드 등과 함께 사용할 수 있다.
    
    
• removeFirst() 메소드는 Set 의 첫번째 요소를 삭제한다.
  
  
  • Set 은 순서가 지정되지 않은 컬렉션이므로, 초기화시 배열의 첫번째 요소와 다를 수 있다.
    
    
• removeAll(), removeAll(keepCapacity:) 메소드는 전체 요소를 삭제한다.
  
  
  • keepCapacity 는 bool 타입의 값으로, true 인 경우 Set 의 용량(capacity)은 감소하지 않는다.
  • removeAll() 메소드를 제외하고는 capacity 가 감소하지 않았다.

var stringSet1: Set<String> = ["A", "B", "C", "D"]
// {"A", "D", "B", "C"}

// 특정 요소 삭제
stringSet1.remove("A")

// 특정 인덱스의 요소 삭제
if let idx = stringSet1.firstIndex(of: "C") {
    stringSet1.remove(at: idx)
}

// Set 의 첫번째 요소 삭제 
stringSet1.removeFirst() // "D" 가 삭제된다.

// Set 의 모든 요소 삭제 
stringSet1.capacity // 6 :: 4 + 2(여유공간)
stringSet1.removeAll(keepingCapacity: true)
stringSet1.capacity // 6으로 함수 호출전과 같다.

 

✔︎ Set 요소 정렬해서 반복하기

• for ... in 문법으로 Set 의 요소를 순회할 수 있다. 이때 지정된 순서는 없다.
• Set.sorted() 메소드 호출로 Set을 오름차순으로 정렬할 수 있다. 정렬된 배열이 반환된다.
• Set.sorted(by: {$0 > $1 }) 메소드 호출로 Set 을 내림차순으로 정렬할 수 있다. 정렬된 배열이 반환된다.

var nameSet: Set<String> = ["Sally", "Mary", "Michael", "Brown"]

// Set 요소 반복문으로 순회하기
// Michael - Brown -Sally - Mary 순서로 순회되었다.
for name in nameSet {
    print(name)
}

// Set 요소 정렬해서 반복 순회하기
// Brown - Mary - Michael - Sally 으로 알파벳 사전순으로 정렬된다.
for name in nameSet.sorted() {
    print(name)
}

// Set 요소 내림차순으로 정렬하기
// ["Sally", "Michael", "Mary", "Brown"]
nameSet.sorted(by: { $0 > $1 }))

 

💡 Set 집합 연산 함수 이용하기

Set 은 수학에서의 집합 개념을 기반으로 만든 타입으로, 집합 구조나 연산이 필요할 때 적용하면 좋은 타입입니다. 두 집합간 연산을 위해 합집합, 교집합, 여집합, 차집합 메소드를 제공합니다. 각 연산마다 새로운 Set 을 만들어 반환하는 메소드, 원본 Set 을 업데이트 하는 메소드 이렇게 두 개가 존재해요! 메소드의 인자는 Array, Set 모두 가능합니다.

 

• Set 의 동등연산 (==) 는 내부 요소가 같으면 동등하다고 판단합니다. 순서가 없기 때문에 요소만 비교하는 것입니다.
  
  
• 합집합 (A∪B) :: 두 집합에 있는 요소를 모두 포함시킨다.
  
  
  • union(_:) 메소드는 두 Set 의 합집합으로 새로운 Set 을 만들어 반환한다.
  • formUnion(_:) 메소드는 두 Set 의 합집합으로 원본 Set 을 업데이트한다.
  • A.formUnion(B) = A 에 없는 B의 요소를 추가한다.
    
    
• 교집합 (A∩B) :: 두 집합에 공통적으로 있는 요소를 포함시킨다.
  
  
  • intersection(_:) 메소드는 두 Set 의 교집합으로 새로운 Set 을 만들어 반환한다.
  • formIntersection(_:) 메소드는 두 Set 의 교집합으로 원본 Set 을 업데이트한다.
  • A.formIntersection(b) = A 에 있는 B의 요소를 삭제한다.
    
    
• 여집합 (A∪B - A∩B) :: 두 집합의 전체 집합에서 두 집합에 공통으로 있는 요소를 제외한다.
  
  
  • symmetricDifference(_:) 메소드는 두 Set 의 여집합으로 새로운 Set 을 만들어 반환한다.
  • formSymmetricDifference(_:) 메소드는 두 Set 의 여집합으로 원본 Set 을 업데이트한다.
    
    
• 차집합 (A-B) :: A 집합에서 B 집합의 원소를 제외한다.
  
  
  • subtracting(_:) 메소드는 원본 Set 에서 주어진 Set 에 포함되지 않는 원소로 새로운 Set 을 만들어 반환한다.
  • subtract(_:) 메소드는 원본 Set 에서 주어진 Set 의 원소를 삭제한다.

// Set 연산
var A: Set = ["A", "B", "C", "D"]
let B: Set = ["C", "D", "E", "F"]

// 합집합 ["B", "E", "D", "A", "C", "F"]
let unionSet = A.union(B)

// 교집합 ["C", "D"]
let intersectionSet = A.intersection(B)

// 여집합 ["B", "E", "A", "F"]
let complementSet = A.symmetricDifference(B)

// 차집합 ["B", "A"]
let subtractSet = A.subtracting(B)

합집합 / 교집합 / 여집합 / 차집합

 

✔︎ Set 의 도우미 메소드들

• isSubset(of:) 메소드는 원본 Set 이 주어진 Set 의 부분 집합인지 확인해 Bool 값을 반환한다.
  
  
• isStrictSubset(of:) 메소드는 동등한 Set 이 아닌 부분 집합인지 확인해 Bool 값을 반환한다.
  
  
  • 부분집합이 아니거나 동등할 경우 False, 동등하지 않고 부분집합인 경우 True
• isSuperset(of:) 메소드는 원본 Set 이 주어진 Set 의 상위집합인지 확인해 Bool 값을 반환한다.
  
  
  • isSubset 메소드와 반대되는 개념이다.
• isStrictSuperset(of:) 메소드는 동등한 Set 이 아닌 상위 집합인지 확인해 Bool 값을 반환한다.
  
  
• isDisjoint(with:) 메소드는 두 Set 의 공통 요소가 없는지 확인해 Bool 값을 반환한다.
  
  
  • 공통요소가 없으면 True , 공통요소가 있으면 False
    
    

let A: Set = ["A", "B", "C", "D"]
let B: Set = ["C", "D", "E", "F"]
let C: Set = ["A", "B"]

// 부분집합인지 비교하기
A.isSubset(of: C) // false
C.isSubset(of: A) // true

// 완전한 부분집합인지 비교하기
let D: Set = ["A", "B", "C", "D"]
B.isStrictSubset(of: A) // false
C.isStrictSubset(of: A) // true
D.isStrictSubset(of: A) // false

// 상위집합인지 비교하기
A.isSuperset(of: C) // true
A.isStrictSuperset(of: D) // false

// 공통요소가 없는지 확인하기
A.isDisjoint(with: C) // false
A.isDisjoint(with: ["E", "F"]) // true

---

참고 링크

• [Swift 문서] Collection Types

• [민소네님 블로그] [Swift] Set 정리