[Python] 프로그래머스 - [1차] 뉴스 클러스터링

1. 문제 - 프로그래머스 [1차] 뉴스 클러스터링

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

 

💡 문제 접근 방식

자카드 유사도란, A와 B 집합의 교집합 크기  / A와 B 집합의 합집합 크기이다.

이때 주의할 점은 다중집합이기 때문에 중복되는 원소는 제거되는 것이 아니라 집합에 그대로 남아있다.

 

문제의 예시를 보면

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

 

교집합에는 A와 B 집합 모두 들어있는 원소는 각 집합의 해당 원소의 갯수의 최소값 만큼 들어가고,

(예를들어 1을 보자. A와 B 모두 1이 들어있고, A에는 2개 B는 1개 들어가있으므로 최소값인 1개만큼 교집합에 들어간다.)

합집합에는 각 집합의 해당 원소의 갯수의 최대값 만큼 들어간다.

A와 B 둘중 한 집합에만 들어있는 원소들은 모두 합집합에 들어간다.

 

❌ 틀린 풀이

def solution(str1, str2):
    answer = 0
    s1 = [str1[i:i+2].lower() for i in range(len(str1)-1) if str1[i:i+2].isalpha()]
    s2 = [str2[j:j+2].lower() for j in range(len(str2)-1) if str2[j:j+2].isalpha()]
    
    if s1 == s2:
        return 65536
        
    bunja, bunmo = 0, 0
    
    for s in s1:
        if s in s2:
            bunja += min(s1.count(s), s2.count(s))
            bunmo += max(s1.count(s), s2.count(s))
        else:
            bunmo += s1.count(s)
            
    for s in s2:
        if s not in s1:
            bunmo += s2.count(s)
    
    return int(bunja/bunmo * 65536)

 

먼저, 차례대로 2글자씩 자른 문자열이 isalpha() 인지를 확인하고, 모두 소문자로 만들어 배열로 만드는 부분은 모든 풀이에 공통적으로 해당된다.

- isalpha(): 기타 공백, 숫자, 특수 문자가 들어가있는 경우 해당 쌍을 버리므로, 이런 문자들은 alphabet으로 인지하지 않기 때문에 isalpha()인 2글자 문자열만 걸러낼 수 있다.

- lower(): 원소를 비교할 때, 대문자와 소문자 차이를 비교하지 않으므로 lower() 혹은 upper()로 모두 소문자, 대문자화 해준다.

 

틀린부분은 반복문 안에서 매번 count로 원소의 갯수를 세는 것에 있다.

예를 들어 s1 = ['ab', 'ab', 'bc'], s2 = ['ab', 'bc', 'bc']인 경우를 생각해보면, 교집합에 ab는 1개, bc는 2개 들어가야하지만

매번 원소의 갯수를 세서 추가하기때문에 위 코드에서는 ab가 1인 경우를 2번 더해버린다.

 

따라서, Counter 를 통해 각 원소의 갯수를 센 다음 중복없이 최소값, 최대값을 계산하여 갯수를 세야한다.

 

✅ 풀이 1

from collections import Counter

def solution(str1, str2):
    s1 = [str1[i:i+2].lower() for i in range(len(str1)-1) if str1[i:i+2].isalpha()]
    s2 = [str2[i:i+2].lower() for i in range(len(str2)-1) if str2[i:i+2].isalpha()]
    
    bunja, bunmo = 0, 0
    dic1 = Counter(s1)
    dic2 = Counter(s2)
    
    for k, v in dic1.items():
        if k in dic2:
            bunja += min(v, dic2[k])
            bunmo += max(v, dic2[k])
        else:
            bunmo += dic1[k]
            
    for k, v in dic2.items():
        if k not in dic1:
            bunmo += v
            
    if bunja == 0 and bunmo == 0:
        return 65536
    
    return int(bunja/bunmo * 65536)

 

✅ 풀이 2

Counter 객체 또한 집합처럼 교집합, 합집합, 차집합이 가능하다...!!!!!

Counter의 교집합: A와 B에서 겹치는 원소의 경우, 더 작은 갯수의 원소로 합쳐짐

합집합: A와 B에서 겹치는 원소의 경우, 더 큰 갯수의 원소로 합쳐짐

from collections import Counter

def solution(str1, str2):
    s1 = [str1[i:i+2].lower() for i in range(len(str1)-1) if str1[i:i+2].isalpha()]
    s2 = [str2[i:i+2].lower() for i in range(len(str2)-1) if str2[i:i+2].isalpha()]
    
    c1 = Counter(s1)
    c2 = Counter(s2)
    
    if not c1 and not c2:
        return 65536
        
    # c1 & c2: 교집합 / c1 | c2 : 합집합
    return int(float(sum((c1&c2).values()))/float(sum((c1|c2).values())) * 65536)