[python] 합집합, 교집합, 차집합, 대칭차, 다중 집합의 합집합, 교집합까지 총 정리 / 파이썬 중복 집합

python

 

포스팅 목차 

1. 파이썬 리스트 합집합, 교집합, 차집합, 대칭차 정리 

2. 파이썬 리스트 다중 집합의 합집합, 교집합 정리

3. 2018 카카오 블라인드 코딩테스트에 쓰인 다중 집합 합집합, 교집합 분석 

 

 

2018년 kakao blind 코딩 테스트 문제 [ 1차 뉴스 클러스터링 ] 을 풀면서 다중 집합이라는 개념을 처음 알게되었다. 겸사겸사 공부겸 정리해보고 요 개념이 어떻게 코딩테스트에 나왔는지도 분석해보기 ! 

 

아래 코드는 리스트를 기준으로 작성했지만 set을 기반으로 (?) 변형시킨 것이기 때문에 set의 합집합, 교집합, 차집합, 대칭차집합이라고 볼 수 있다. 

 

 

 

 

 

1. Python, 파이썬 리스트 합집합, 교집합, 차집합, 대칭차 정리 

 

 

 

 

합집합

list a와 b 를 set으로 중복을 제거하고 | 기호로 합쳐서 list로 만든다. 리스트의 덧셈 뺄셈이 아닌 set으로 변형시킨 후, 더하고 뺄 수 있다. 

a = [1, 2, 3, 4, 5]
b = [3, 4, 5, 6, 7]

union = list(set(a) | set(b))
print(union)  # [1,2,3,4,5,6,7]
union_set = (set().union(a, b))
print(union_set)  # {1,2,3,4,5,6,7}
union2 = list(set().union(a, b))
print(union2)  # [1,2,3,4,5,6,7]

 

 

 

 

 

 

 

 

교집합

파이썬 리스트의 교집합은 각각 리스트 a,b 를 set으로 중복을 제거한 다음 & 기호를 사용해서 a에도 b 에도 있는 요소 = 교집합을 찾아 list 에 넣는다.

set(a).intersection(b)- 교집합과  set().union(a,b) -합집합의 코드의 리스트 위치가 조금 다른 점 주의 !!! 

a = [1, 2, 3, 4, 5]
b = [3, 4, 5, 6, 7]

intersection = list(set(a) & set(b))
print(intersection)  # [3,4,5]

intersection_set = set(a).intersection(b)
print(intersection_set)

intersection2 = list(set(a).intersection(b))
print(intersection2)  # [3,4,5]

 

 

 

 

 

 

 

 

차집합

합집합 | , 교집합 &, 그리고 차집합은  -   그냥 빼기 기호와 같아서 가장 이해하기가 쉬운 차집합이다.

a = [1, 2, 3, 4, 5]
b = [3, 4, 5, 6, 7]

subtractionA_B = list(set(a) - set(b))
print(subtractionA_B)  # [1,2]

subtractionB_A = list(set(b) - set(a))
print(subtractionB_A)  # [6,7]

subtractionA_B2 = list(set(a).difference(b))
print(subtractionA_B2) # [1,2]

subtractionB_A2 = list(set(b).difference(a))
print(subtractionB_A2)  # [6,7]

 

 

 

 

 

 

대칭차집합 

아래 코드 중 list2와 같이 합집합에서 교집합을 빼도 되지만 ^ 기호를 쓰면 아주 간단하게 해결할 수 있다!  파이썬은 이런 점에서 참 편리한 언어인 것 같다. 

* symmetric difference 여집합의 합 (교집합 제외한 나머지 합) 

set(a).symmetric_difference(b) 함수를 써도 가능하다. 합집합의 경우 (set().union(a,b)) 만 제외하면 교집합, 차집합, 대칭차집합 모두 set(a).매서드(b) 라는 형식을 가지고 있다. 

a = [1, 2, 3, 4, 5]
b = [3, 4, 5, 6, 7]


list1 = list(set(b) ^ set(a))
print(list1)  # [1,2,6,7]

list2 = list((set(a)|set(b))-(set(a)&set(b)))
print(list2)  # [1,2,6,7]

list3 = list(set(a).symmetric_difference(b))
print(list3) # [1,2,6,7]

list4 = list(set(b).symmetric_difference(a))
print(list4) # [1,2,6,7]

 

 

---

 

 

2. 파이썬 리스트 다중 집합의 합집합, 교집합 정리

다중 집합이란 ? 

일반 집합의 예시는 위의 코드들과 같다. 다중 집합이란 아래 예시를 보면 이해가 더 빠르다 ! 

a = [1, 1, 2, 2, 3]
b = [1, 2, 2, 4, 5]

일반집합의 합집합 : [1,2,3,4,5]
일반집합의 교집합 : [1,2]

다중집합의 합집합 : [1,1,2,2,3,4,5]
다중집합의 교집합 : [1,2,2]

위와 같이 다중 집합의 합집합은 a와 b 리스트의 합집합이되 중복이 허용된다. 

 

 

 

다중 집합의 합집합 

 

먼저 a를 깊은 복사로 a1, a2에 담는다. a1 = a2 = a.copy() 하게되면 a1과 a2의 메모리에 저장되는 주소가 같아져버려서 꼭 따로 따로 만들어 준다. 

 

b의 요소 하나 하나 for 문으로 가져온다. 만약 b의 첫 번째 요소가 a1 리스트 안에 있지 않다면 a2 (a와 같은 요소들 리스트) 에 해당 b의 첫 번째 요소 값을 추가해 준다.

 

만약 b의 첫 번째 요소가 a1의 리스트 안에 있다면 추가하지 않아도 된다. 이 때, 주의할 점은 추가를 안하지만 꼭 a1 리스트의 해당 b요소를 삭제해주어 다음 번 b의 요소가 (첫 번째 요소와) 동일 시 a1리스트의 안에 없기때문에 a2에 추가하여 다중 집합을 가능하게 한다. 

 

a2 가 결국 합집합으로 만들 answer 리스트 ! 미리 a 리스트의 값을 넣고 b의 요소 값을 추가하는 방식이다. 

a = [1, 1, 2, 2, 3]
b = [1, 2, 2, 4, 5]

a1 = a.copy()
a2 = a.copy()
for i in b:
    if i not in a1:
        a2.append(i)
    else:
        a1.remove(i)

print(a2)

# 짧게 표현하기

a1 = a.copy(); a2 = a.copy()
for i in b:
    a2.append(i) if i not in a1 else a1.remove(i)

print(a2)

 

 

 

 

다중 집합의 교집합 

 

아래 코드에서 a의 복사 리스트를 만들지 않았는데 이유는 이 코드 이후에 바로 답 제출이었어서 a 리스트의 요소가 변경되어도 상관없었기 때문이다. 그래서 코드가 좀 더 단순하다 ! 위의 코드도 리스트 변경해도 되는 상황이면 copy()를 굳이 해줄 필요 없이 바로 변수에 remove해주면 된다. 

 

코드 해설 : b 의 요소 i 를 for 반복문으로 불러와서 만약 해당 요소가 a 리스트에 있다면 common 리스트에 b 요소를 담고 (i)  그 다음 요소를 비교하기 위해 a 리스트에 방금 담은 b의 요소 i를 제거해 준다. 

 

a = [1, 1, 2, 2, 3]
b = [1, 2, 2, 4, 5]

common = []
for i in b:
    if i in a:
        a.remove(i)
        common.append(i)

print(common)


#짧은 코드 
a = [1, 1, 2, 2, 3]
b = [1, 2, 2, 4, 5]

common = []

for i in b:
    if i in a: a.remove(i); common.append(i)

print(common)

 

---

 

일반 교집합 , 합집합을 이용하여 다중집합의 합집합, 교집합 구하기 

 

풀이 해설 : 일반적인 교집합 gyo, 합집합 hap 을 구하기. 각 요소별 a, b 리스트의 요소의 개수를 구하기. 교집합인 경우 min() 함수 사용, 합집합인 경우 max() 함수 사용한다. 

 

다중 교집합 경우 교집합의 첫 요소 1은 a리스트에 2 개, b리스트에 1개가 있다. min(1,2) == 1 이므로 A 리스트에 1을 담는다. 교집합 두 번째 요소 2는 a리스트에 2개, b 리스트에 2개가 있다. min(2,2) == 2 이므로 A리스트에 2를 두 번 담는다 ==> [1,2,2] 

 

다중 합집합의 경우 합집합의 첫 요소 1은 a리스트에 2개 b리스트에 1개가 있다. max(2,1) ==2 이므로 B리스트에 1 (i ) 을 두 번 담는다. 반복...... ==> [1,1,2,2,3,4,5] 

 

a = [1, 1, 2, 2, 3]
b = [1, 2, 2, 4, 5]

gyo = set(a) & set(b) # {1,2}
hap = set(a) | set(b) # {1,2,3,4,5}

A = []
for i in gyo:
    for _ in range(min(a.count(i),b.count(i))):
        A.append(i)

print(A)  # [1,2,2]

B = []
for i in hap:
    for _ in range(max(a.count(i), b.count(i))):
        B.append(i)

print(B)   # [1,1,2,2,3,4,5]

 

 

일반 교집합 , 합집합을 이용하여 다중집합의 합집합, 교집합의 개수 구하기 

 

sum을 써서 해당 min or max의 개수를 합친다 ! 

gyo_sum = sum([min(a.count(i), b.count(i)) for i in gyo])

print(gyo_sum)  # 3

hap_sum = sum([max(a.count(i),b.count(i)) for i in hap])

print(hap_sum)  # 7

 

 

 

---

 

 

 

3. 2018 카카오 블라인드 코딩테스트에 쓰인 다중 집합 합집합, 교집합 분석 

 

해당 문제 내용 및 문제 풀이 

https://codingpractices.tistory.com/47

[프로그래머스] 파이썬 [1차] 뉴스 클러스터링 / 2018 카카오 kakao blind 코딩 테스트 문제 풀이