[Programmers/Py] 뉴스 클러스터링

문제

문제바로가기

나의 코드

from collections import Counter

def solution(str1, str2):

    def getList(str):
        result = []
        
        for i in range(len(str) - 1):
            temp = str[i:i+2]
            if temp.isalpha():
                result.append(temp.lower())
        
        return result

    
    # 리스트 만들기
    list1 = getList(str1)
    list2 = getList(str2)
    print(list1, list2)

    # 교집합 크기 구하기
    and_size = 0
    and_counter = Counter(list1) & Counter(list2)
    for k in and_counter:
        and_size += and_counter[k]
    
    # 합집합 크기
    or_size = len(list1) + len(list2) - and_size

    # 자카드유사도 구하기
    if or_size <= 0: j = 1
    else:
        j = and_size / or_size

    return int(j*65536)

나의 알고리즘

입력값이 아래와 같다고 가정한다.

# 예시1
str1 = "aa1+aa2"
str2 = "AAAA12"

# 예시2
str1 = "FRANCE"
str2 = "french"

1. 리스트 만들기
문자열을 두 글자씩 끊어서 다중집합의 원소로 만든다.

# 예시1
list1 = ['aa', 'aa']
list2 = ['aa', 'aa', 'aa']

# 예시2
list1 = ['fr', 'ra', 'an', 'nc', 'ce'] 
list2 = ['fr', 're', 'en', 'nc', 'ch']

2. 교집합 크기 구하기
집합끼리 &연산을 해서 교집합을 구할 수 있지만, 문제에서 자카드 유사도는 원소의 중복도 허용할 수 있어야 하므로 이 방법은 옳지 않다. 따라서 Counter를 사용하여 중복을 허용하는 교집합을 구하였다.

1. 카운터로 변환시킨 후

# 예시1
Counter({'aa': 2})
Counter({'aa': 3})

# 예시2
Counter({'fr': 1, 'ra': 1, 'an': 1, 'nc': 1, 'ce': 1}) 
Counter({'fr': 1, 're': 1, 'en': 1, 'nc': 1, 'ch': 1})

2. 카운터 객체끼리 교집합연산을 시킨다.

# 예시1) 교집합 연산 결과
Counter({'aa': 2})

# 예시2) 교집합 연산 결과
Counter({'fr': 1, 'nc': 1})

3. Counter객체의 모든 value를 더한 값이 교집합 크기이다.

# 예시1의 교집합 크기
2

# 예시2의 교집합 크기
2 = 1 + 1

3. 합집합 크기 구하기
합집합의 크기 = list1의 크기 + list2의 크기 - list1과 2의 교집합 크기

4. 자카드유사도 구하고 값 리턴하기

다른 풀이

import re

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 int((gyo_sum/hap_sum)*65536)

• 교집합 크기 구하기

1. 문자열을 2글자씩 끊고 이를 리스트로 만든다.
2. 중복을 허용하지 않는 집합set()으로 변환 후, &연산으로 교집합을 구한다.
3. 2에서의 집합을 순회한다.
   1. 해당 요소가 1번 리스트에서 등장하는 횟수를 센다. count()
   2. str1과 str2중에 이 횟수가 더 작은 값이 중복된 횟수이다.
   3. 이 횟수를 모두 더한 값이 교집합의 크기이다.

• 합집합 크기 구하기
  교집합 크기 구하는 방법과 비슷하다. 다만, 3-2에서 횟수가 더 큰 값을 더해주면 된다.

Comment

문제를 이해하는것은 어렵지 않았지만, 원소의 중복을 허용하는 다중집합을 구현하는 것이 포인트인 문제였다.