이번에 해결해 볼 문제는 프로그래머스에 있는 [1차] 뉴스 클러스터링이다.
문제 설명
원소의 중복을 허용하는 다중집합에 대하여 자카드 유사도를 구하면 된다.
$A$ = {1, 1, 2, 2, 3}, $B$ = {1, 2, 2, 4, 5}인 경우
- $A\cap B$ = {1, 2, 2}, $A\cup B$ = {1, 1, 2, 2, 3, 4, 5}
- $J(A, B) = 3/7$
자카드 유사도를 문자열에 적용
- 앞에서부터 두 글자씩 끊어서 하나의 원소를 구성
- 단, 대문자와 소문자의 차이는 무시하며 영문자로 구성된 글자쌍만 유효하다.
문제 해결 아이디어
집합 문제이므로 집합 연산을 통해 문제를 해결할 수 있다.
- 하지만 다중집합이므로 python의 집합 자료형을 사용할 수는 없다.
- 따라서 dictionary 자료형을 통해 직접 교집합의 수와 합집합의 수를 구해야 한다.
Dictionary 자료형이 아닌 set 연산을 지원하는 Counter를 사용할 수도 있다. (해당 방법이 더 적합하다고 판단)
문제 해결 코드
1. 첫 번째 나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def make_set(s):
"""
다중집합을 dictionary로 구현하는 함수
"""
set1 = {}
for i in range(len(s)-1):
new_s = s[i:i+2]
if new_s.isalpha():
if not new_s in set1.keys():
set1[new_s] = 0
set1[new_s] += 1
return set1
def make_similarity(arr1, arr2):
"""
교집합의 수와 합집합의 수를 구해서 자카드 유사도를 구하는 함수
"""
common = 0
union = sum(list(arr1.values())+list(arr2.values()))
for key1, val1 in arr1.items():
if key1 in arr2.keys():
min_val = min(val1, arr2[key1])
common += min_val
union -= min_val
return int(common/union * 65536)
def solution(str1, str2):
set1 = make_set(str1.lower())
set2 = make_set(str2.lower())
if not set1 and not set2:
return 65536
return make_similarity(set1, set2)
2. 더 나은 두 번째 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import Counter
def make_list(s):
set1 = []
for i in range(len(s)-1):
new_s = s[i:i+2]
if new_s.isalpha():
set1.append(new_s)
return set1
def solution(str1, str2):
list1 = make_list(str1.lower())
list2 = make_list(str2.lower())
set1 = Counter(list1)
set2 = Counter(list2)
if not set1 and not set2:
return 65536
# Counter는 set 연산을 지원한다.
common = set1 & set2
union = set1 | set2
similarity = sum(common.values()) / sum(union.values())
return int(similarity * 65536)