다중집합
수학에서 집합(set)은 어떤 조건을 만족시키는 서로 다른 대상의 모임으로, 집합 내 원소에 대해 중복을 허용하지 않는다.
반면 multiset(중복집합, 다중집합)은 각 원소를 어떤 기수만큼 중복하는 것을 허용하는 집합의 일반적인 개념이다.
원소가 중복된 횟수를 중복도(multiplicity)라고 하는데, 일반적인 집합은 각 원소의 중복도가 1인 중복집합이라고 생각할 수도 있다.
이 글에서는 Python으로 중복집합의 교집합과 합집합 연산을 구현한 코드를 정리한다. 프로그래머스 - [1차] 뉴스 클러스터링 문제 맞다…….
교집합
아래와 같은 중복집합 A, B가 있다고 할 때,
a = [1, 2, 2, 3, 4, 5]
b = [1, 1, 2, 3, 4, 6]두 중복집합 A, B의 교집합은 [1, 2, 3, 4]가 된다.
구현은 간단하다. 중복집합 A를 순회하면서 원소가 B에 있는지 확인하고, B에 원소가 존재하면 결과 중복집합에 추가한다. 추가한 원소는 더 처리되지 않도록 B에서 제거한다.
def intersection(a, b):
result = []
for i in a:
if i in b:
b.remove(i)
result.append(i)
return result
실행 결과
a = [1, 2, 2, 3, 4, 5]
b = [1, 1, 2, 3, 4, 6]
print(intersection(a, b))
합집합
마찬가지로 중복집합 A, B가 있다고 할 때,
a = [1, 2, 2, 3, 4, 5]
b = [1, 1, 2, 3, 4, 6]두 중복집합 A, B의 합집합은 [1, 1, 2, 2, 3, 4, 5, 6]가 된다.
구현 방식은 한 집합의 차집합을 구한 뒤, 다른 집합과 합쳐서 반환하는 것이다.
예로 들어 A에서 B에 대한 차집합을 구하고, B와 합쳐서 반환하는 방식으로 구현한다면 다음과 같이 구현할 수 있다.
1. A와 B의 원소를 비교할 수 있도록 B를 복사하여 변수 b_temp 에 저장한다.
2. 중복집합 A를 순회하면서 b_temp에 원소가 존재하는지 확인한다. 원소가 존재하지 않으면 결과 집합 result에 원소를 추가하고, 원소가 존재하면 b_temp에서 원소를 제거한다. 이 때 집합 result는 A에서 B에 대한 차집합에 해당한다.
3 반복이 끝나면 result와 집합 B 원본을 합쳐서 반환한다.
def union(a, b):
result = []
b_temp = b.copy()
for i in a:
if i not in b_temp:
result.append(i)
else:
b_temp.remove(i)
return sorted(result + b)
🤔 이렇게 직접 구현하는 방법도 있지만, 최근에 정리했던 Python 공식 문서를 확인해보니 collections.Counter 클래스가 multiset과 유사하다고 한다……!
이후에는 collections.Counter로 다중집합 연산하는 방법을 정리하면 좋을 것 같다.
참고 문서
https://medium.com/nerd-for-tech/lets-implement-sets-multisets-e91eefb4e1c2