5. 뉴스 클러스터링(난이도: 중) - Python3.6.1

 

1.풀이방법

 

딕셔너리(Dict)를 이용해서 풀어봤다.

A = {1, 1, 2, 2, 3} , B = {1, 2, 2, 4, 5}

A = 1:2개  B = 1:1개 

 2:2개        2:2개

 3:1개      

      4:1개

      5:1개

A ∩ B = {1, 2, 2} => 1:1개,2:2개 - 공통되는것중 개수가 적은쪽 기준 

A ∪ B = {1, 1, 2, 2, 3, 4, 5} => 1:2개,2:2개,3:1개,4:1개,5:1개 - 모든항목 개수가 많은쪽 기준

2.코드

 

import collections

def Question5(str1,str2):

    if not(len(str1) >= 2 and len(str1) <= 1000): #1

        return 'out of range!'

    if not(len(str2) >= 2 and len(str2) <= 1000):

        return 'out of range!'

    str1 = str1.upper() #2

    str2 = str2.upper()

    collect1 = collections.defaultdict(int) #3

    collect2 = collections.defaultdict(int)

    collectList = set('') #4

    

    for i in range(len(str1)-1): #5

        if str1[i].isalpha() and str1[i+1].isalpha():

            collect1[str1[i]+str1[i+1]] += 1

            collectList.add(str1[i]+str1[i+1])

    for i in range(len(str2)-1):

        if str2[i].isalpha() and str2[i+1].isalpha():

            collect2[str2[i]+str2[i+1]] += 1

            collectList.add(str2[i]+str2[i+1])

    intersectionCount = 0

    unionCount = 0

    for i in collectList:  #6

        if collect1[i]>0 and collect2[i]>0: #교집합 카운트

            if collect1[i] < collect2[i]:

                intersectionCount += collect1[i]

            else:

                intersectionCount += collect2[i]

        if collect1[i] > collect2[i]: #합집합 카운트

            unionCount += collect1[i]

        else:

            unionCount += collect2[i]

    if intersectionCount == 0 or unionCount == 0: #7

        result = 65536

    else: #8

        result = int(intersectionCount/unionCount*65536)

            

    return result

3.코드설명

 

#1 입력된 두개의문자열(str1,str2)이 길이를 초과할 경우 'out of range!'반환

#2 AB,Ab,ab 모두 같은 원소로 취급하기때문에 대문자로 통일

#3 원소를 담을 데이터사전 생성

#4 교집합,합집합 계산할때 사용할 다중집합(중복허용x)

#5 원소 두개가 알파벳일경우 데이터사전에 추가한다.

#6 다중집합에 있는 원소만큼 반복문을 돌면서 교집합,합집합 개수를 구한다.

#7 교집합,합집합이 모두 공집합일경우 자카드유사도 1*65536 을 반환한다. 

#8 교집합/합집합*65536 계산후 소수점 아래를 버리고 정수만 출력한다.

4.결과

>>> Question5('FRANCE','french')

16384

>>> Question5('handshake','shake hands')

65536

>>> Question5('aa1+aa2','AAAA12')

43690

>>> Question5('E=M*C^2','e=m*c^2')

65536