[알고리즘] 프로그래머스 - 뉴스 클러스터링

프로그래머스 - 뉴스 클러스터링

내 풀이

from collections import defaultdict

def solution(str1, str2):
    dict1 = defaultdict(int)
    dict2 = defaultdict(int)
    dict1_total = 0
    dict2_total = 0

    str1 = str1.lower()
    str2 = str2.lower()

    for i in range(2, len(str1) + 1):
        if str1[i-2].isalpha() and str1[i-1].isalpha():
            dict1[str1[i-2:i]] += 1
            dict1_total += 1

    for i in range(2, len(str2) + 1):
        if str2[i-2].isalpha() and str2[i-1].isalpha():
            dict2[str2[i-2:i]] += 1
            dict2_total += 1

    if dict1_total == 0 and dict2_total == 0:
        return 1 * 65536

    common_keys = set(dict1.keys()).intersection(dict2.keys())
    common_total = 0
    each_total = 0
    for key in common_keys:
        common_total += min(dict1[key], dict2[key])
        each_total += max(dict1[key], dict2[key])

    for key in dict1.keys():
        if key not in common_keys:
            each_total += dict1[key]

    for key in dict2.keys():
        if key not in common_keys:
            each_total += dict2[key]

    similarity = int(common_total / each_total * 65536)
    return similarity

print(solution("FRANCE", "french") == 16384)
print(solution("handshake", "shake hands") == 65536)
print(solution("aa1+aa2", "AAAA12") == 43690)
print(solution("E=M*C^2", "e=m*c^2") == 65536)

처음에는 집합이라고 해서 바로 set를 썼는데 set를 쓰면 안된다. 왜냐하면 여기서 교집합과 합집합은 중복이 허용되기 때문이다.

다른 사람 풀이

def solution(str1, str2):
    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if str1[i:i+2].isalpha()]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if str2[i:i+2].isalpha()]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0:
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)

파이써닉하게 엄청 잘 푼 풀이다. 만약 중복이 허용되게 집합을 합치거나 공통 부분을 추출하고 싶으면 &나 |를 사용하자.