프로그래머스 > 뉴스 클러스터링 (Python 3) | Counter, 다중 집합

1. 문제 설명

유사한 기사를 묶는 기준으로 "자카드 유사도"라는 방법을 채택했다.

 

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있는데, 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

 

이러한 자카드 유사도를 원소의 중복을 허용하는 다중집합에 대해서 확장한다.

- 예1)

다중집합 A는 원소 1을 3개 가지고 있고 (A = {1, 1, 1}), 다중집합 B는 원소 1을 5개 가지고 있다 (B = {1, 1, 1, 1, 1}). 이 다중집합의 교집합은 원소 1을 min(3, 5)인 3개, 합집합은 원소 1을 max(3, 5)인 5개 가지게 된다.

 

- 예2)

다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합은 {1, 2, 2}, 합집합은 {1, 1, 2, 2, 3, 4, 5}이므로 자카드 유사도는 3/7이다.

 

이를 문자열을 두 글자씩 끊어서 다중집합으로 만든 것에 응용하고자 한다.

- 예)

문자열 "France"와 "French"가 주어졌을 때, 이를 두 글자씩 끊어서 다중 집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로 자카드 유사도는 2/8이다.

 

 

2. 입력 형식

- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

 

- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.

 

 

3. 코드

(1) Counter 사용하기

from collections import Counter

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(len(str2)-1):
        if str2[i:i+2].isalpha():
            arr2.append(str2[i:i+2])
    
    # 중복 원소 고려를 위해 Counter 사용
    arr1_counter = Counter(arr1)
    arr2_counter = Counter(arr2)
    
    # 합집합, 교집합 구하기
    hab = list((Counter1 & Counter2).elements())
    kyo = list((Counter1 | Counter2).elements())
	
    # 집합 A, B가 모둔 공집합일 경우 J(A, B) = 1
    if len(union) == 0 and len(inter) == 0:
        return 65536
    else:
        return int(len(inter) / len(union) * 65536)

 

 

(2) 다중 집합 사용하기

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(len(str2)-1):
        if str2[i:i+2].isalpha():
            arr2.append(str2[i:i+2])
    
    # 다중 집합 구하기
    arr1_result = arr1.copy() # 합집합
    intersection = [] # 교집합

    for i in arr2:
        if i in arr1:
            arr1.remove(i)
            intersection.append(i)
        else:
            arr1_result.append(i)
    
    if len(arr1_result) == 0 and len(intersection) == 0:
    	return 65536
    else:
    	return int(len(intersection) / len(arr1_result) * 65536)

 

 

4. 해설

(0) 공통

- 대문자와 소문자 구분이 없도록 string.lower() 함수로 문자열을 소문자로 변경해준다.

- 두 글자씩 끊어서 원소로 만들 때 영문자로 된 글자 쌍만 유효하도록 string.isalpha() 함수로 검토한다.

 

 

(1) Counter 사용하기

- 중복된 원소를 고려하기 위해서 원소의 개수를 Counter로 구한다.

- Counter는 '|', '&' 연산이 가능하다. 이때, 핵심은 Counter.elements()이다.

Counter.keys()를 하면 중복된 값이 존재해도 중복 없이 unique한 값이 반환된다. 따라서, elements()를 통해 중복된 개수만큼을 리스트로 저장한다.

 

 

(2) 다중 집합 사용하기

- 일반적인 Python의 집합은 중복 원소를 허용하지 않는다. 하지만, 다중 집합은 중복된 원소를 포함하기 때문에 실제로는 리스트에 저장하여 나타낸다.

 

- 마치 Sorting에서 stable sorting이 있고, unstable sorting이 있는 것처럼 생각하면 쉽다! 같은 '1'이지만 '1_a', '1_b'가 있는 것으로 생각하는 것이다.

 

- 다중집합에서 교집합과 합집합을 구하는 방법은 다음과 같다.

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

a_temp = a.copy()
a_result = a.copy()

for i in b:
	if i not in a_temp:
    		a_result.append(i)
      	else:
        	a_temp.remove(i)

a_temp는 a - b (차집합)이 되고, a_result는 합집합이 된다.

교집합은 a_result에서 a_temp 원소를 뺀 원소들이 된다.

 

 

a_temp가 필요한 이유는, a에서 remove 해버리면 원본 데이터가 손실되기 때문이다.

이 문제에서는 이후에 arr1이 필요하지 않아서 바로 arr1에서 remove를 한 것이다.

 

arr1_result = arr1.copy() # 합집합
intersection = [] # 교집합

for i in arr2:
    if i in arr1:
        arr1.remove(i)
        intersection.append(i)
    else:
        arr1_result.append(i)

 

 

---

reference : https://velog.io/@munang/%EA%B0%9C%EB%85%90%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4%EC%A4%91-%EC%A7%91%ED%95%A9