[프로그래머스/Python파이썬] 뉴스 클러스터링(2018 카카오 코딩테스트 1차)

문제 링크: programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

 

문제 설명

두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다. 

(합집합의 크기) = (A의 크기 + B의 크기 - 교집합의 크기) 식이 만족하기 때문에 결국 자카드 유사도는 다음과 같이 정의할 수 있다. 

J(A, B) = (교집합의 크기) / (A의 크기 + B의 크기 - 교집합의 크기)

즉, 교집합의 크기만 구하면 답을 구할 수 있다. 

 

다중집합으로 처리하기 위해 문자열을 리스트로 변환해서 저장했다. 변환 과정에서 영문자의 경우 모두 소문자로 바꿔서 저장했다. (대문자와 소문자를 같은 문자로 취급하기 위함) 

 

주의할 점은 A, B가 모두 공집합인 경우 J(A, B)를 1로 문제에서 정의하고 있기 때문에 이 부분을 따로 처리해주어야 한다. 

 

그리고 두 집합의 교집합 크기를 구하는 함수를 작성해서 자카드 유사도를 구하고 65536을 곱해서 반환했다. 교집합 크기는 두 다중집합 A, B 중에서 더 크기가 작은 것을 집합으로 놓고(중복성을 제거하고) 교집합을 찾았다. 어떤 원소 x가 A와 B에 모두 속하는 경우 A, B에서 x가 더 적게 포함된 수를 교집합 크기에 더했다. 

 

 

 

 

 

소스코드

def numIntersection(A, B):
    n = 0   # A와 B의 교집합 원소 개수
    # A의 원소 개수 <= B의 원소 개수
    for x in set(A):
        if x in B:  # x가 A와 B 모두에 속하는 경우
            n += min(A.count(x), B.count(x))
    return n;

def solution(str1, str2):
    answer = 0
    # 모든 문자열을 소문자로 바꾸고 다중집합 생성
    str1 = str1.lower()
    str2 = str2.lower()
    A, B = [], []
    for i in range(len(str1) - 1):
        # 영문자인 경우에만 다중집합의 원소로 포함
        if str1[i].isalpha() and str1[i + 1].isalpha():
            A.append(str1[i] + str1[i + 1])
    for i in range(len(str2) - 1):
        if str2[i].isalpha() and str2[i + 1].isalpha():
            B.append(str2[i] + str2[i + 1])
    # A, B 모두가 공집합인 경우 자카드 유사도는 1
    if (not A) and (not B): return 65536
    # 교집합 원소의 개수 구하기
    n = numIntersection(A, B) if len(A) < len(B) else numIntersection(B, A)
    answer = n / (len(A) + len(B) - n)

    return int(answer*65536)