뉴스 클러스터링

프로그래머스

자카드 유사도 구하기.

• 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
• 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
• 자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.
• 이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다.
• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다.

입출력

str1	str2	answer
FRANCE	french	16384
handshake	shake hands	65536
aa1+aa2	AAAA12	43690
E=M*C^2	e=m*c^2	65536

---

접근 방식

• str1, str2를 모두 대문자로 만들고 두글자씩 알파벳만 끊어서 리스트에 담는다.
• 다중집합이 허용되므로 set()자료형을 쓰지 않고,
  for문과 if문을 활용하여 교집합의 개수를 구한다.
  이 때 공통으로 속하는 원소는 크기가 더 큰 집합에서 삭제한다.
• 교집합을 제거한 집합과 나머지 집합을 합쳐서 합집합의 개수를 구한다.
• 자카드 유사도를 구한다.

알게된 점

• 집합의 크기가 더 큰 집합에서 교집합을 삭제해야한다.
• 원소를 삭제할 집합이 아닌 집합의 원소를 기준으로 for문을 돌려야한다.

코드

def set_ele(string):
    string = string.upper()
    ans = []
    for i in range(len(string)-1):
        s = string[i]+string[i+1]
        if s.isalpha():
            ans.append(s)
    return ans
        

def find_rel(A, B):
    # 교집합 
    if len(A) > len(B):
        inter = [A.remove(x) for x in B if x in A]
    else:
        inter = [B.remove(x) for x in A if x in B]
    a = len(inter)
    b = len(A+B)
    return a, b

    
def solution(str1, str2):
    # 두 글자씩 끊기
    string1 = set_ele(str1)
    string2 = set_ele(str2)
    # 교집합 개수, 합집합 개수 구하기
    a, b = find_rel(string1, string2)
    if a==0 or b==0:
        return 65536
    else:
        return int(a*65536/b)