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

문제

뉴스 클러스터링

문제 해설

주어진 두 문자열에 대해 자카드 유사도를 구하는 문제이다.
set을 사용하여 문제를 풀 수 있는데, set은 중복을 허용하지 않기 때문에 딕셔너리를 만들어 두 글자 문자열에 대한 count를 처리해 주었다.

• 두 문자열을 lower 혹은 upper를 취해 소문자 혹은 대문자로만 이뤄진 문자열로 바꿔준다.
• 각 문자열을 두 글자씩 끊어 소문자 혹은 대문자인 경우만 집합에 저장한다. 이때, 딕셔너리에도 같이 저장해 주는데 중복된 문자열의 개수를 세는 용도이다.

• ex) str1 = handshake	str2 = shake hands	

dict1	dict2	set1	set2
{'HA': 2, 'AN': 1, 'ND': 1, 'DS': 1, 'SH': 1, 'AK': 1, 'KE': 1}	{'SH': 1, 'HA': 2, 'AK': 1, 'KE': 1, 'AN': 1, 'ND': 1, 'DS': 1}	{'AN', 'HA', 'ND', 'AK', 'DS', 'SH', 'KE'}	{'AN', 'HA', 'ND', 'AK', 'SH', 'DS', 'KE'}

• 두 집합의 합집합과 교집합을 만든다.

union	intersection
{'SH', 'AK', 'ND', 'AN', 'DS', 'KE', 'HA'}	{'SH', 'DS', 'AK', 'ND', 'AN', 'KE', 'HA'}

• 합집합은 두 딕셔너리중 큰 값, 교집합은 작은 값을 가져와 더한뒤, 계산을 한다.

소스 코드

def solution(str1, str2):
    str1 = str1.upper()
    str2 = str2.upper()
    set1 = set()
    set2 = set()
    dict1 = dict()
    dict2 = dict()
    for i in range(len(str1) - 1):
        if 65 <= ord(str1[i]) <= 90 and 65 <= ord(str1[i + 1]) <= 90:
            s = str1[i] + str1[i + 1]
            dict1.setdefault(s, 0)  # key가 없으면 key넣고 0으로 초기화
            dict1[s] += 1
            set1.add(s)

    for i in range(len(str2) - 1):
        if 65 <= ord(str2[i]) <= 90 and 65 <= ord(str2[i + 1]) <= 90:
            s = str2[i] + str2[i + 1]
            dict2.setdefault(s, 0)  # key가 없으면 key넣고 0으로 초기화
            dict2[s] += 1
            set2.add(s)
    # 둘다 공집합인 경우
    if len(dict1) == 0 and len(dict2) == 0: 
        return 65536
        
    union = set(set1 | set2)
    intersection = set(set1 & set2)
    union_cnt = 0
    intersection_cnt = 0
    
    for x in union:
        if x not in dict1:
            union_cnt += dict2[x]
            continue
        if x not in dict2:
            union_cnt += dict1[x]
            continue
        union_cnt += max(dict1[x], dict2[x])
    for x in intersection:
        intersection_cnt += min(dict1[x], dict2[x])

    return int(intersection_cnt / union_cnt * 65536)