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

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

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

 

str1, str2 의 다중집합을 만든다. 이때 만들어지는 집합은 중복을 허용한다. 그래서 makeSet 에서 return 되는 값은 list 이다.

 

교집합과 합집합을 구한 뒤(set() 은 중복허용을 하지 않는다.) 중복을 허용하므로

교집합의 한 원소 e 는 list 인 s1 과 s2 에 들어있는 개수 중 가장 적은 개수만큼 교집합에 속한다.

반대로, 합집합의 한 원소 e는 list 인 s1 과 s2 에 들어있는 개수 중 가장 많은 개수만큼 합집합에 속한다.

 

즉, 교집합의 길이 = sum([min(s1.count(i), s2.count(i)) for i in (set(s1) & set(s2))])

합집합의 길이 = sum([max(s1.count(i), s2.count(i)) for i in (set(s1) | set(s2))])

를 이용하여 자카드 유사도에서 65336을 곱한 값을 출력한다. (단, U 가 0 이면 65336)

 

import re

def makeSet(string):
    return list(filter(lambda x : re.search('[^a-z]', x) == None, [string.lower()[i:i+2] for i in range(len(string)-1)]))

def solution(str1, str2):
    answer = 0
    s1, s2 = makeSet(str1), makeSet(str2)
    I = sum([min(s1.count(i), s2.count(i)) for i in (set(s1) & set(s2))])
    U = sum([max(s1.count(i), s2.count(i)) for i in (set(s1) | set(s2))])

    answer = int(I / U * 65536) if U != 0 else 65536

    return answer

print(solution('FRANCE', 'french')) # 16384