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

[1차] 뉴스 클러스터링

문제 설명

뉴스 클러스터링

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

풀이

Counter를 이용해서 각 집합별 원소의 개수를 센다.

만약 str1과 str2의 공통 원소일 경우 교집합에는 각 집합 별 해당 원소의 갯수의 min 값을 합집합에는 각 집합 별 해당 원소의 갯수의 max 값을 넣는다. 공통 원소가 아닐 경우 합집합에 더해준다.

처음에 7 9 10 11 테스트 케이스를 통과하지 못했는데, 합집합 로직이 문제였다.

반례는 아래와 같았다.

str1: " abc" str2: "abbb" return: 16384

합집합 = ['ab', 'bc', 'bb', 'bb'] (o) 합집합 = ['ab', 'bc', 'bb'] (x)

위의 예시처럼 중복 원소가 합집합에서 빠지는 문제가 있어서 합집합에 포함되지 않은 나머지 원소들도 더해줬더니 해결됐다.

from collections import Counter
def solution(str1, str2):
    answer = 0
    # 다 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    # 두 글자씩 끊어서 집합 만들기 (영문자인 글자 쌍만)
    str1 = [str1[i: i + 2] for i in range(len(str1)) if len(str1[i: i + 2]) > 1 and ''.join(str1[i: i + 2]).isalpha()]
    str2 = [str2[i: i + 2] for i in range(len(str2)) if len(str2[i: i + 2]) > 1 and ''.join(str2[i: i + 2]).isalpha()]
     
    # 둘 다 공집합일 경우 자카드 유사도 1
    if len(str1) == 0 and len(str2) == 0 :
        return 65536
      
    # 각 집합의 원소별 갯수 세기
    str1_cnt = Counter(str1)
    str2_cnt = Counter(str2)
    
    intersection = 0 # 교집합 원소의 개수
    union = 0 # 합집합 원소의 개수
    
    tmp = [] # 합집합 원소 저장
    for k in str1_cnt.keys():
        if k in str2_cnt.keys(): # 공통원소일 경우 
            intersection += min(str1_cnt[k], str2_cnt[k])
            union += max(str1_cnt[k], str2_cnt[k])
            tmp.append(k)
            continue
        union += str1_cnt[k]
        tmp.append(k)
    
    for k in str2: # str2에서 합집합에 포함하지 않은 원소 합집합에 더하기
        if k not in tmp:
            union += 1
            
    return int((intersection / union) * 65536)

다른 사람 풀이

집합을 이용한 풀이

import re
def solution(str1, str2):
    str1 = [str1[i: i + 2].lower() for i in range(len(str1) - 1) if not re.findall('[^a-zA-Z]+', str1[i: i + 2])]
    str2 = [str2[i: i + 2].lower() for i in range(len(str2) - 1) if not re.findall('[^a-zA-Z]+', str2[i: i + 2])]
    
    union = set(str1) | set(str2)
    intersection = set(str1) & set(str2)
    
    if len(union) == 0:
        return 65536
    
    union = sum([max(str1.count(u), str2.count(u)) for u in union])
    intersection = sum([min(str1.count(i), str2.count(i)) for i in intersection]) 
    
    print(union, intersection)
    return int((intersection/union) * 65536)

집합 자료구조를 이용해 합집합과 교집합을 구한 다음 각 원소들을 원래 배열에서 갯수를 세서 비교한다.