[프로그래머스/파이썬] [1차] 뉴스 클러스터링

내 풀이

import re

def solution(str1, str2):
    # 대소문자 구분 없이
    str1 = str1.lower()
    str2 = str2.lower()
	
    def to_multi_set(string):
        # 문자열을 앞에서부터 2개씩 묶어 집합을 구성할 원소 생성하는 함수
        d = {}
        for i in range(len(string)-1):
            s = string[i:i+2]
            # 영어가 아니면 (특수문자 혹은 공백) 원소에서 제외
            if re.sub('[A-Za-z]','A', s) != 'AA':
                continue
            if s in d.keys():
                d[s] += 1
            else:
                d[s] = 1
        return d, set(d.keys())  # 원소와 그 개수를 나타내는 dict, 원소 집합 set
    
    def jaccard(tms1, tms2):
    	# to_multi_set에서 나온 값을 활용해 최종 jaccard 유사도 계산
        d1, s1 = tms1
        d2, s2 = tms2
        
        # 둘 다 공집합일 경우 값은 1
        if not s1 and not s2:
            return 1
        
        # i : 교집합 , u : 합집합
        i = s1.intersection(s2)
        u = s1.union(s2)
        
        # 분자에 해당하는 교집합 계산
        numerator = 0
        for _i in i:
            n_i1 = 0 if not _i in d1.keys() else d1[_i]
            n_i2 = 0 if not _i in d2.keys() else d2[_i]
            numerator += min(n_i1,n_i2)
            
        # 분모에 해당하는 합집합 계산
        denominator = 0
        for _u in u:
            n_u1 = 0 if not _u in d1.keys() else d1[_u]
            n_u2 = 0 if not _u in d2.keys() else d2[_u]
            denominator += max(n_u1,n_u2)

        return numerator/denominator # 최종 jaccard 유사도
    
    tms1 = to_multi_set(str1)
    tms2 = to_multi_set(str2)

    return int(jaccard(tms1, tms2) * 65536) # 문제에서 요구한 65,536 곱한 후 정수 부분만 처리

 

메모

직관적으로 이해 가는 방식으로 코드를 작성하니 작성 자체에는 시간이 들지 않았으나

효율성을 따졌다면 매우 비효율적이었을 것 같다.