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

kiki·2022년 2월 24일
1

프로그래머스

목록 보기
7/79

문제 링크

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개수)
그걸 사용한 풀이다.

  • 위의 두개가 집합과 다른 다중집합의 특징을 나타내는 부분이다.
  • set과 집합 연산, 그리고 count를 활용해 문제를 간단히 풀었다.
  • 감탄 떡볶이

정리

  • 다중집합을 배웠다. 단지 요소의 중복이 가능하다는 것 빼고는 기존 집합과 다를 것이 없다. 단지 중복이 가능하기 때문에 교집합과 합집합의 갯수를 구하는 부분이 다르게 느껴졌을 뿐

0개의 댓글