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

---

문제설명

https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

사고과정

• 해쉬를 사용해 풀이를 했다. 주의해야 할 점은 문제에서 자카드 유사도를 설명해주고 구하는 공식을 설명해주는데, 이 때 '원소의 중복을 허용하는 다중집합' 일 경우를 고려해야 하기 때문에 섣불리 집합자료구조(set)으로 하게 되면 구현할 수가 없다고 생각했다.
• 우선 주어진 집합 각 A, B에 대한 해쉬를 만들어서 원소를 키로하고 카운트값을 밸류로 하는 딕셔너리를 만든다. 그리고 두 집합에 대해 교집합, 합집합을 담는 리스트를 두 개 정의한다. 이 때, 두 집합 A, B에 들어있는 모든 원소 하나씩 loop를 돌면서 교집합에 들여보낼지, 합집합에 들여보낼지 결정한다.
• 결정할 때, 원소 값을 카운트한 A, B의 해쉬를 사용하는데, 만약 특정 원소가 A, B 둘다 원소이면서 둘 중에 최소 카운트 수를 갖고 있는 만큼 반복을 돌아 교집합에 원소를 추가해준다(이 때 A, B 카운트 같아도!) 그리고 A, B 둘다 원소이면서 둘 중에 최대 카운트 수를 갖고있는 만큼 반복을 돌아 합집합에 원소를 추가해준다.
• 마지막으로 A또는 B에만 원소가 있을 경우에는 모두 합집합에 넣어주면 된다
• 그리고 만들어진 합집합, 교집합 리스트의 len 함수를 사용해서 자카드 유사도를 계산해준다. 이 때, 두 리스트 원소가 모두 같거나 또는 둘 다 모두 비어있으면 자카드 유사도는 1로 처리해주는 로직도 추가해준다.

풀이

def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    set1 = dict()
    set2 = dict()
    
    for i in range(len(str1)-1):
        val = str1[i:i+2]
        if val.isalpha():
            set1[val] = set1.get(val, 0) + 1
    for i in range(len(str2)-1):
        val = str2[i:i+2]
        if val.isalpha():
            set2[val] = set2.get(val, 0) + 1
            
    inter = []
    union = []
    elements = set(list(set1.keys()) + list(set2.keys()))
    
    for e in elements:
        if e in set1.keys() and e in set2.keys():
            set1_v, set2_v = set1[e], set2[e]
            if set1_v <= set2_v:
                for _ in range(set1_v): # 최소 개수 -> 교집합
                    inter.append(e)
                for _ in range(set2_v): # 쵀대 개수 -> 합집합
                    union.append(e)
            else:
                for _ in range(set2_v): # 최소 개수 -> 교집합
                    inter.append(e)
                for _ in range(set1_v): # 최대 개수 -> 합집합
                    union.append(e)
        # 합집합
        elif e in set1.keys(): # A만 있을경우
            for _ in range(set1[e]):
                union.append(e)
        elif e not in set1.keys(): # B만 있을 경우
            for _ in range(set2[e]):
                union.append(e)
                
    # 공집합이거나 교집합 == 합집합일 경우
    if inter == union:
        answer = 1
    else:
        answer = len(inter) / len(union)
        
    return int(answer * 65536