[프로그래머스] 뉴스 클러스터링

문제

'자카드 유사도'는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A,B 사이의 자카드 유사도 J(A,B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의한다.
집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A,B) = 1로 정의한다.
이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다.

입력형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 'ab+'가 입력으로 들어오면, 'ab'만 다중집합의 원소로 삼고, 'b+'는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다.

출력형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

풀이

maps = { 원소: [str1에서의 개수, str2에서의 개수] }

• 합집합 : 각 원소에서 최대값의 합
• 교집합 : 각 원소에서 최소값의 합

코드

def solution(str1, str2):
    maps = {} # 집합A, 집합B
    
    makeSet(maps, str1, 0)
    makeSet(maps, str2, 1)
    
    union, inter = 0, 0 # 합집합의 개수, 교집합의 개수
    for item in maps.values():
        inter += min(item)
        union += max(item)
    
    if union == 0: return 65536
    return int((inter/union) * 65536)

def makeSet(sets, strs, index):
    for s in range(len(strs)-1):
        if check(strs[s]) and check(strs[s+1]):
            tmp = (strs[s] + strs[s+1]).lower()
            if tmp in sets:
                sets[tmp][index] += 1
            else:
                sets[tmp] = [0,0]
                sets[tmp][index] = 1
                
def check(c):
    return 'a'<=c<='z' or 'A'<=c<='Z'