[ Lv 2 ] 뉴스 클러스터링

- 구현 문제

- 대/소 구분 없다 하였으므로 소문자로 모두 치환 및 두자리씩 끊어서 알파벳으로만 이루어진 경우 유사도 집합을 만들어 줌. 이 때 딕셔너리 타입으로 개수만 저장해 둔다. set1[두자리 문자]=나타난 개수

- 교집합의 경우는 하나의 딕셔너리를 잡고, 키들을 두 개의 딕셔너리에 따라 값을 비교한 뒤 최솟값을 더해주면 된다. 단, 키에 대응하는 값이 없는 경우는 0으로 간주

- 합집합의 경우는 두개의 딕셔너리를 모두 보면서, 최댓값을 더해주면 된다.

- 마지막으로 두 딕셔너리의 키가 모두 0인 경우는 유사도 1로 간주하라고 문제에서 나타났으므로, 1 * 65536 = 65536으로 써주고, 아닌 경우는 교집합의 수 / 합집합의 수 * 65536을 해준 뒤 int 함수를 사용해서 소숫점을 버리면 된다.

def solution(str1, str2):
    answer = 0
    str1 = str1.lower()
    str2 = str2.lower()

    set1 = {}
    set2 = {}

    # 유사도 집합 만드는 과정(str1, str2)
    for i in range(len(str1) - 1):
        if str1[i:i+2].isalpha():
            if set1.get(str1[i:i+2]) != None:
                set1[str1[i:i+2]] += 1
            else:
                set1[str1[i:i+2]] = 1

    for i in range(len(str2) - 1):
        if str2[i:i+2].isalpha():
            if set2.get(str2[i:i+2]) != None:
                set2[str2[i:i+2]] += 1
            else:
                set2[str2[i:i+2]] = 1

    intersects = 0
    union = 0
    visited = set()

    # 합집합, 교집합의 원소 개수 구하는 과정
    for k in set1.keys():
        if set2.get(k) != None:
            intersects += min(set1.get(k), set2.get(k))
        t1 = set1.get(k)
        t2 = 0 if set2.get(k) == None else set2.get(k)
        union += max(t1, t2)
        visited.add(k)


    for k in set2.keys():
        if k not in visited:
            visited.add(k)
            union += set2.get(k)

    # 유사도 계산
    if len(set1.keys()) == 0 and len(set2.keys()) == 0:
        answer = 65536
    else:
        answer = int(intersects * 65536 / union)  

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges