이번 글에서는 Python의 내장 set 클래스를 사용하지 않고, 다음과 같은 메서드를 가진 집합(Set) 데이터 구조를 직접 구현해 보겠습니다.
- 생성자(Constructor) : 집합의 새 인스턴스를 생성합니다.
- add(val) : 정수 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을 삽입합니다.s.add(10)→ 10은 이미 집합에 있으므로 아무 일도 일어나지 않습니다.s.exists(10)→ 10이 존재하므로 True를 반환합니다.s.remove(10)→ 10을 삭제합니다.s.exists(10)→ 10이 삭제되었고, 동일한 요소는 한 번만 저장될 수 있으므로 False를 반환합니다.s.exists(20)→ 20이 존재하므로 True를 반환합니다.
구현 접근 방식
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 생성자를 정의합니다.
- buckets := 빈 딕셔너리(defaultdict)로 초기화하며, 여기에 데이터 목록을 저장합니다.
- add() 함수를 정의합니다. 인자로 val을 받습니다.
- exists(val)가 False인 경우, buckets[val]의 끝에 val을 추가합니다.
- exists() 함수를 정의합니다. 인자로 val을 받습니다.
- val이 buckets[val]에 있으면 True, 그렇지 않으면 False를 반환합니다.
- remove() 함수를 정의합니다. 인자로 val을 받습니다.
- buckets[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
마무리
이처럼 Python의 내장 set 클래스를 사용하지 않고도 defaultdict를 활용하면 중복을 허용하지 않는 집합 데이터 구조를 손쉽게 구현할 수 있습니다. 각 메서드가 해시 기반 딕셔너리를 사용하기 때문에 평균적으로 O(1) 시간 복잡도로 빠른 삽입, 검색, 삭제가 가능하다는 점도 큰 장점입니다.