[PS] 뉴스 클러스터링

문제 링크

코드

from collections import defaultdict

def solution(str1, str2):
    dict1 = get_dictionary(str1)
    dict2 = get_dictionary(str2)
    
    inter_keys = set(dict1.keys()) & set(dict2.keys())
    inter = {x: min(dict1[x], dict2[x]) for x in inter_keys}
    
    sum_keys = set(dict1.keys()) | set(dict2.keys())
    sums = {x: max(dict1[x], dict2[x]) for x in sum_keys}
    
    if len(sums) == 0:
        return 65536
    return int((sum(inter.values()) / sum(sums.values())) * 65536)


def get_dictionary(s):
    s = s.lower()
    arr = [x + y for x, y in zip(s[:-1], s[1:])]
    dic = defaultdict(int)
    
    for v in arr:
        if not v.isalpha():
            continue
        if v in dic:
            dic[v] += 1
        else:
            dic[v] = 1
    return dic

리뷰

• defaultdict의 사용법에 대해 알아봐야겠다.
• 다른 사람들의 풀이에서는 dictionary를 만들지 않고 set으로 만든 후, 리스트에서 원소의 개수를 세는 방식을 이용했다. 풀이는 훨씬 간단해 보이지만 set을 이용한 풀이는 원소의 개수를 세는 과정에서 O(n^2)의 시간 복잡도를 가지지만 내 풀이는 dictionary로 변환하는 과정에서 한번만 순회하기 때문에 O(n)의 시간 복잡도를 가진다.