[Programmers] 뉴스 클러스터링

뉴스 클러스터링

뉴스 클러스터링 를 클릭하면 바로 이동한다.

자카드 유사도를 구하는 문제이다.

문자열을 조건에 맞게 집합으로 바꾼 후

합집합 원소 의 수, 교집합 원소의 수를 구하면 됐다.

분명히 다른 사람들은 정규식을 이용해 주어진 문자열 중 알파벳만 2개씩 뽑아 집합을 만들 것 이다.

하지만 나는 정규식이 익숙치 않기 때문에 코드를 짜 만들어 주었다.

다음으로 크기가 작은 집합의 원소를 돌면서 크기가 큰 집합에 있다면 교집합 크기를 1 더해준 뒤 모든 집합에서 값을 지운다.

그리고 각 집합에 남아있는 원소 개수와 교집합 크기를 더하면 합집합 크기가 된다.

---

from copy import deepcopy


def solution(A, B):
	A = A.upper()
	B = B.upper()
	A_set = []
	B_set = []

	for idx in range(len(A) - 1):
		if A[idx].isalpha() and A[idx + 1].isalpha():
			A_set.append(A[idx] + A[idx + 1])

	for idx in range(len(B) - 1):
		if B[idx].isalpha() and B[idx + 1].isalpha():
			B_set.append(B[idx] + B[idx + 1])

	if len(A_set) == 0 and len(B_set) == 0:
		return 65536

	same_cnt = 0
	if len(A_set) <= len(B_set):
		for val in deepcopy(A_set):
			if val in B_set:
				same_cnt += 1
				A_set.remove(val)
				B_set.remove(val)
	else:
		for val in deepcopy(B_set):
			if val in A_set:
				same_cnt += 1
				A_set.remove(val)
				B_set.remove(val)

	all_cnt = len(A_set) + len(B_set) + same_cnt
	answer = int(same_cnt / all_cnt * 65536)
	return answer

중간에 두 집합이 모두 공집합이라면 나눗셈이 가능하지 않아 유사도는 1이 된다.

다중집합 때문에 당연히 set 을 이용해서 풀 수 없다고 생각했다.

하지만 다른 사람 코드를 보니 set 을 이용해서도 풀 수 있다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.

다중집합 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가 된다.

문제에서 다중집합을 설명하며 보여준 예시이다.

이 개념을 사용하면 set 을 이용해 풀 수있다..

역시 문제에서 준 개념은 모두 사용을 해야한다는게 맞다 !!!

---

import re
import math

def solution(str1, str2):
    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0 :
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)