다음 방법을 사용하여 집합 데이터 구조를 구현한다고 가정합니다. -
- 집합의 새 인스턴스를 생성하는 생성자
- 집합에 정수 val을 삽입하는 add(val)
- exists(val) val이 집합에 있는지 여부를 확인합니다.
- remove(val)를 사용하여 집합에서 val을 제거합니다.
따라서 집합 s를 구성하면 s.add(10), s.add(20), s.add(10), s.exists(10), s.remove(10), s.exists( 10), s.exists(20), 출력은
- s.add(10)의 경우 10을 삽입합니다.
- s.add(20)의 경우 20을 삽입합니다.
- 10은 이미 s에 있으므로 아무 일도 일어나지 않습니다.
- s.exists(10)은 10이 있으면 true를 반환합니다.
- s.remove(10)로 10개 삭제
- s.exists(10)은 10이 제거되고 하나의 요소가 한 번만 존재할 수 있기 때문에 false를 반환합니다.
- s.exists(20)는 20이 존재하므로 true를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 생성자를 정의합니다.
- buckets :=빈 지도이며 여기에는 데이터 목록이 저장됩니다.
- add() 함수를 정의합니다. 시간이 걸립니다
- 존재하는(val)이 거짓이면
- 버킷 끝에 val 삽입[val]
- exist() 함수를 정의합니다. 시간이 걸립니다
- val이 버킷[val]에 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
- remove() 함수를 정의합니다. 시간이 걸립니다
- 버킷 삭제[val]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict class MySet: def __init__(self): self.buckets = defaultdict(list) def add(self, val): if not self.exists(val): self.buckets[val].append(val) def exists(self, val): return val in self.buckets[val] def remove(self, val): del self.buckets[val] s = MySet() s.add(10) s.add(20) s.add(10) print(s.exists(10)) s.remove(10) print(s.exists(10)) print(s.exists(20))
입력
s = MySet() s.add(10) s.add(20) s.add(10) s.exists(10) s.remove(10) s.exists(10) s.exists(20)
출력
True False True