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

kiki·2022년 2월 24일

level2 python 코테

프로그래머스

목록 보기

7/78

문제 링크

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

문제 설명

문제를 간단하게 설명하자면 다중집합으로 확장한 자카드 유사도를 구현하는 것이다. 두개의 문자열이 주어졌을때 각 문자열은 2-gram으로 쪼갠 다중집합에서 자카드 유사도를 구하는 것이다.

이어서 채원이의 야매 설명 (정확한 것은 구글링을 필요로 합니다...)

자카드 유사도란?
집합이 두개 주어졌을때 두 집합의 교집합 크기를 합집합 크기로 나눈것
n-gram이란?
2-gram을 예시로 들어 설명하면 "뉴스 클러스터링" 이란 문장이 주어졌을때 2-gram을 적용(?) 하면 ["뉴스","스 "," 클", "클러", "러스","스터","터링"] 으로 2 글자씩 쪼개지는 것을 말한다.
다중집합이란?
중복을 허용하는 집합을 말한다.

1차 시도

def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    arr_str1 = [str1[i]+str1[i+1] for i in range(len(str1)-1) if((str1[i]+str1[i+1]).isalpha())]
    arr_str2 = [str2[i]+str2[i+1] for i in range(len(str2)-1) if((str2[i]+str2[i+1]).isalpha())]
    union = arr_str1 + arr_str2 #합집합
    inter = [i for i in arr_str1 if(i in arr_str2)] #교집합
    for i in inter:
        union.remove(i)
    if(len(union)==0 and len(inter)==0):
        return 65536
    elif(len(union)==0):
        return 0
    else:
        return int(len(inter)/len(union)*65536)

처음에 고민끝에 다중집합에 대해 조금 찾아보고 작성한 코드이다. 틀린 부분은 바로바로
교집합을 구하는 부분이었다. 다중집합의 교집합이 약간 헷갈리는 부분이 있어서 코드를 잘못 작성했었다. 지금 생각해보니까 그냥 집합의 교집합이랑 다를게 없긴 한데... 게슈탈트 붕괴온다.
-암튼 다중집합을 더 찾아보니 틀렸구나! 해서 다시 시도했다.

2차 시도

def solution(str1, str2):
    inter = []
    arr_str1 = [str1[i:i+2].lower()for i in range(len(str1)-1) if((str1[i:i+2]).isalpha())]
    arr_str2 = [str2[i:i+2].lower() for i in range(len(str2)-1) if((str2[i:i+2]).isalpha())]
    union = arr_str1 + arr_str2 #합집합
    for i in arr_str1:
        if(i in arr_str2):
            inter.append(i)
            arr_str2.remove(i)
    for i in inter:
        union.remove(i)
    if(len(union)==0 and len(inter)==0):
        return 65536
    elif(len(union)==0):
        return 0
    else:
        return int(len(inter)/len(union)*65536)

바뀐 부분은 교집합을 구하는 부분과 lower을 n-gram구하는 부분에 적용해준 것.
교집합을 구하는 데에서 for in을 사용하는 것은 적절한 방법이 아니다.
교집합은 같은게 있으면 교집합 리스트에 추가해주고 기존 비교 배열에서 해당 값은 제거해준다.
합집합은 집합 두개 더하고, 교집합의 요소들을 제거해주면 된다.
지금 생각해보니 교집합, 합집합 구하는 부분은 그냥 집합이랑 다를게 없다. 설명.. 필요 없겠는걸.
그냥 다중집합이 중복을 허용하기 때문에 set을 일차원적으로 사용하는게 불가능한 문제였다.

다른 사람의 풀이

import re
import math

def solution(str1, str2):
    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0 :
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)

문제에 힌트가 있었다. 바로 다중집합의 교집합 요소 x의 교집합에서의 갯수는 min(str1에서 x개수, str2에서 y개수)
다중집합의 합집합의 요소 x의 합집합에서의 갯수는 max(str1에서 x개수, str2에서 x개수)
그걸 사용한 풀이다.