[프로그래머스/Level 2] 뉴스클러스터링 - python

뉴스 클러스터링

문제내용 유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다. 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다. 이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다. 입력방식 - 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다. - 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다. - 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

---

프로그래밍 순서

 

1. 다중집합을 만드는 함수 만들기

  1-1 index 순서대로 2개의 문자열을 가지는 문자 생성

  1-2 생성한 문자에 특수문자가 존재하지 않고 문자의 개수가 2일 경우에만 리스트에 넣음.

  1-3 (1-1 ~ 1-2) 과정을 문자열의 index 마지막까지 확인

  1-4 문자가 들어간 리스트 반환

2. 교집합을 구하는 함수 만들기

  2-1 2개의 리스트를 집합으로 변환 후 교집합 구함

  2-2 2개의 집합에서의 교집합의 원소들의 개수를 찾아서 작은 숫자를 변수에 저장

  2-3 작은 숫자들의 반복해서 더해진 변수 저장

3. 교집합을 구하는 함수 만들기

  3-1 2개의 리스트를 집합으로 변환 후 합집합 구함

  3-2 2개의 집합에서의 교집합의 원소들의 개수를 찾아서 큰 숫자를 변수에 저장

  3-3 큰 숫자들의 반복해서 더해진 변수 저장

4. solution 함수 짜기

  4-1 각 문자열의 다중집합 구하기

  4-2 구한 다중집합들 간의 교집합 구하기

  4-3 구한 다중집합들 간의 합집합 구하기

  4-4 합집합이 0이면 65536 반환

  4-5 int(교집합/합집합*65536) 수 반환

---

전체코딩

- pytest 모듈을 이용해서 코드가 원하는 정답이 나오는지 바로 확인 가능

- pytest 사용법

pip install -U pytest
pytest --version # 설치 확인
 
pytest [python 파일 이름] -s # 올바르게 코딩했다면 PASSED가 뜸

- 코드

def solution(str1, str2):
    multiset1 = make_mutiset(str1)
    multiset2 = make_mutiset(str2)
    i_num = intersection(multiset1, multiset2)
    c_num = combination(multiset1, multiset2)
    if c_num == 0:
        return 65536
    return int(i_num/c_num*65536)
    
def make_mutiset(str):
    multiset = []
    index = 0
    while index != len(str):
        element = str[index:index+2]
        if element.isalpha() and len(element) == 2:
            multiset.append(element.upper())
        index += 1
    return multiset
 
def intersection(multiset1, multiset2):
    num = 0
    i_set = set(multiset1) & set(multiset2)
    for ele in i_set:
        num += min(multiset1.count(ele), multiset2.count(ele))
    return num 
 
def combination(multiset1, multiset2):
    num = 0
    c_set = set(multiset1) | set(multiset2)
    for ele in c_set:
        num += max(multiset1.count(ele), multiset2.count(ele))
    return num
 
def test_answer():
    assert solution("FRANCE", "french") == 16384
    assert solution("handshake", "shake hands") == 65536
    assert solution("aa1+aa2", "AAAA12") == 43690
    assert solution("E=M*C^2", "e=m*c^2") == 65536