[1차] 뉴스 클러스터링

 

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

문제풀이

중복을 허용하는 집합을 만드는 것이 핵심이다. 

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 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가 된다.

 

지문중에서 강조 표시한 부분을 봐보자 힌트가 적혀있다.
교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개
합 A ∪ B는 원소 "1"을 max(3, 5)인 5개

 

그렇다면 알파벳 쌍만 허용되게끔 변환한 str1, str2의 중복을 제거하고 각 요소를 카운트 한뒤 해당 지문의 내용을 인용해서 알고리즘을 구상하면 된다.

def solution(str1, str2):
    a, b = [], []

    def create_set(string, target):
        for i in range(1, len(string)):
            prev, current = string[i - 1], string[i]
            if prev.isalpha() and current.isalpha():
                temp = prev.upper() + current.upper()
                target.append(temp)

    create_set(str1, a)
    create_set(str2, b)

    inter = []
    union = []
    for item in set(a + b):
        count_a = a.count(item)
        count_b = b.count(item)
        inter.extend([item] * min(count_a, count_b))
        union.extend([item] * max(count_a, count_b))

    if not inter and not union:
        return 65536

    return int((len(inter) / len(union)) * 65536)