멀티셋

멀티셋(또는 가방)은 일반 집합과 유사한 데이터 구조이지만, 동일한 요소를 여러 번 저장할 수 있다.

예를 들어, 일반 집합에 요소 1, 2, 2를 추가하면 집합은 두 개의 항목만 포함한다. 두 번째로 2를 추가해도 아무런 영향이 없다.

var set = Set<Int>()
set.add(1) // set은 이제 [1]
set.add(2) // set은 이제 [1, 2]
set.add(2) // set은 여전히 [1, 2]

반면, 멀티셋에 요소 1, 2, 2를 추가하면 세 개의 항목을 포함한다.

var set = Multiset<Int>()
set.add(1) // set은 이제 [1]
set.add(2) // set은 이제 [1, 2]
set.add(2) // set은 이제 [1, 2, 2]

이것이 배열과 매우 비슷해 보일 수 있다. 그렇다면 왜 멀티셋을 사용할까? 두 가지의 차이점을 살펴보자.

• 순서: 배열은 추가된 항목의 순서를 유지하지만, 멀티셋은 순서를 유지하지 않는다.
• 멤버십 테스트: 배열에서 요소가 컬렉션에 속하는지 테스트하는 데 O(N) 시간이 걸리지만, 멀티셋은 O(1) 시간이 걸린다.
• 부분집합 테스트: 컬렉션 X가 컬렉션 Y의 부분집합인지 테스트하는 것은 멀티셋에서는 간단한 작업이지만, 배열에서는 복잡하다.

멀티셋의 일반적인 연산은 다음과 같다.

• 요소 추가
• 요소 제거
• 요소의 개수 확인 (추가된 횟수)
• 전체 집합의 개수 확인 (추가된 항목의 수)
• 다른 멀티셋의 부분집합인지 확인

멀티셋의 실제 사용 사례로는 한 문자열이 다른 문자열의 부분 아나그램인지 확인하는 것이 있다. 예를 들어, "cacti"는 "tactical"의 부분 아나그램이다. (즉, "tactical"의 글자를 재배열하여 "cacti"를 만들 수 있고, 몇 글자가 남는다.)

var cacti = Multiset<Character>("cacti")
var tactical = Multiset<Character>("tactical")
cacti.isSubSet(of: tactical) // true!

구현

이 Multiset 구현체는 내부적으로 딕셔너리를 사용해 각 엘리먼트와 그 추가 횟수를 매핑한다.

핵심 코드는 다음과 같다:

public struct Multiset<Element: Hashable> {
  private var storage: [Element: UInt] = [:]
  
  public init() {}

이 클래스를 사용해 문자열 멀티셋을 생성하는 방법은 다음과 같다:

var set = Multiset<String>()

엘리먼트를 추가할 때는 해당 엘리먼트의 카운터를 증가시키거나, 존재하지 않으면 1로 설정한다:

public mutating func add (_ elem: Element) {
  storage[elem, default: 0] += 1
}

이 메서드를 사용해 앞서 생성한 셋에 엘리먼트를 추가하는 방법은 다음과 같다:

set.add("foo")
set.add("foo") 
set.allItems // ["foo", "foo"] 반환

이제 셋에는 두 개의 엘리먼트가 존재하며, 둘 다 문자열 "foo"다.

엘리먼트를 제거하는 방법은 추가와 유사하다. 엘리먼트의 카운터를 감소시키거나, 제거 전 값이 1이면 내부 딕셔너리에서 제거한다.

public mutating func remove (_ elem: Element) {
  if let currentCount = storage[elem] {
    if currentCount > 1 {
      storage[elem] = currentCount - 1
    } else {
      storage.removeValue(forKey: elem)
    }
  }
}

특정 아이템의 개수를 가져오는 방법은 간단하다. 내부 딕셔너리에서 해당 아이템의 값을 반환한다.

public func count(for key: Element) -> UInt {
  return storage[key] ?? 0
}

Swift Algorithm Club의 Simon Whitaker가 작성