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

문제 링크

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

프로그래머스

 

문제 설명

유사한 기사를 묶는 기준을 정하기 위해서 "자카드 유사도"라는 방법을 찾아냈다. 

자카드 유사도는 집합 간의 유사도를 검사하는 방법 중의 하나로 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다. 집합 A와 B가 모두 공집합일 경우 나눗셈이 정의되지 않으므로 따로 J(A, B) = 1로 정의한다.

입력 형식

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

출력형식

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

 

풀이

str1과 str2를 두 단어씩 끊어서 교집합과 합집합을 구해,

합집합이 0이 아닐 때, (교집합 ÷ 합집합) x 65536 을 하면 되는 문제이다.

 

❌ Code - 실패

import math

def solution(str1, str2):
    two_str1, two_str2 = [], []
    for i in range(len(str1) - 1):
        tmp = str1[i] + str1[i + 1]
        if tmp.isalpha():
            two_str1.append(tmp.lower())
    
    for i in range(len(str2) - 1):
        tmp = str2[i] + str2[i + 1]
        if tmp.isalpha():
            two_str2.append(tmp.lower())
    
    # 교집합과 합집합 구하기
    inter = 0
    for t in two_str1:
        if t in two_str2:
            inter += 1
    union = len(two_str1) + len(two_str2) - inter
    
    if not union:
        return 65536
    else:
        return math.trunc(((inter / union) * 65536))

 

처음, 위의 코드대로 제출했을 때, 테케 4, 7, 9, 10, 11 번이 실패했다.

교집합과 합집합을 구하는 과정에서 반복문을 돌 때, 반례가 발생한다.

ex) str1 = "aa bb bb" , str2 = "aa bb" 일 때, 

교집합 = 2, 합집합 = 3 이여야하지만, 위의 코드대로 실행하면, 교집합 = 3, 합집합 = 2 가 됌.

 

문제를 해결하기 위해, for문을 돌 때 교집합인 경우, two_str2의 요소를 제거하여 문제를 해결했다.

 

✅ Code - 성공

import math

def solution(str1, str2):
    two_str1, two_str2 = [], []
    for i in range(len(str1) - 1):
        tmp = str1[i] + str1[i + 1]
        if tmp.isalpha():
            two_str1.append(tmp.lower())
    
    for i in range(len(str2) - 1):
        tmp = str2[i] + str2[i + 1]
        if tmp.isalpha():
            two_str2.append(tmp.lower())
    
    inter = 0
    for t in two_str1:
        if t in two_str2:
            inter += 1
            two_str2.remove(t) # 교집합 문자열 제거
    union = len(two_str1) + len(two_str2) # 교집합 요소를 제거하므로, inter을 뺄 필요가 없음
    
    if not union:
        return 65536
    else:
        return math.trunc(((inter / union) * 65536))