스토리지
프로그래머스 17677 - 뉴스 클러스터링 본문
https://programmers.co.kr/learn/courses/30/lessons/17677#
코딩테스트 연습 - [1차] 뉴스 클러스터링
뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브
programmers.co.kr
문제 설명 - 구현
앞부분 생략...
유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.
이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.
예제 입출력
str1 | str2 | answer |
FRANCE | french | 16384 |
handshake | shake hands | 65536 |
aa1+aa2 | AAAA12 | 43690 |
E=M*C^2 | e=m*c^2 | 65536 |
- 문자열을 조건에 맞게 2개씩 쪼개서 list안에 삽입
- list의 현 값이 다른 list에도 존재하면 교집합 갯수 + 1을 하고 다른 list에서 해당 원소 삭제
- 합집합 = 두 list의 길이의 합 - 교집합의 갯수
def solution(str1, str2):
answer = 1
str1 = str1.upper()
str2 = str2.upper()
list1 = []
list2 = []
for i, v in enumerate(str1):
if i < len(str1) - 1:
if v.isalpha() and str1[i + 1].isalpha():
tmp = v + str1[i + 1]
list1.append(tmp)
for i, v in enumerate(str2):
if i < len(str2) - 1:
if v.isalpha() and str2[i + 1].isalpha():
tmp = v + str2[i + 1]
list2.append(tmp)
intersect = 0
union = len(list1) + len(list2)
for i in list1:
if i in list2:
list2.remove(i)
intersect += 1
union -= intersect
if intersect == 0 and union == 0:
answer = 1
elif len(list1) == 0 and len(list2) == 0:
answer = 1
else:
answer = intersect / union
return answer * 65536 // 1
'알고리즘' 카테고리의 다른 글
프로그래머스 12952 - N-Queen (0) | 2021.09.15 |
---|---|
프로그래머스 12981 - 영어 끝말잇기 (0) | 2021.09.13 |
프로그래머스 72411 - 메뉴 리뉴얼 (0) | 2021.09.11 |
프로그래머스 42628 - 이중우선순위큐 (0) | 2021.09.10 |
프로그래머스 42626 - 더 맵게 (0) | 2021.09.10 |