코딩테스트 연습 - 뉴스 클러스터링(못품)

[문제]

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.

 

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다.

두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어,
집합 A = {1, 2, 3},
집합 B = {2, 3, 4}라고 할 때,

교집합 A ∩ B = {2, 3},
합집합 A ∪ B = {1, 2, 3, 4}이 되므로,

집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다.

 

집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

 

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.

다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자.

집합 A = {1, 1, 1}
집합 B = {1, 1, 1, 1, 1}

이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개,
합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다.

다중집합
 
A = {1, 1, 2, 2, 3}, 다중집합
B = {1, 2, 2, 4, 5}라고 하면, 교집합
 
A ∩ B = {1, 2, 2}, 합집합
A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로,

자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

 

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다.

문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다.
str1 = {FR, RA, AN, NC, CE},
str2 = {FR, RE, EN, NC, CH}가 되며,
교집합(inter)은 {FR, NC},
합집합(union)은 {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"는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다.

유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

---

[1차 시도] - 21.08.20

조건 1. 특수문자, 숫자 등 영문자 제외한 문자는 허용 x 

조건 2. 대소문자 구분 x

 

두 조건을 충족하도록 문자열을 두 글자씩 끊어서 다중집합으로 만들어준다. 

 

일단은 알파벳인지 아닌지 분별하기 위한 알파벳 리스트를 하나 만들어줬다.

그리고 입력받은 문자열을 lower()메써드를 이용해 모두 소문자로 만들고, 빈 깡통도 두개 만들었다.

 

for문을 통해서 문자열이 알파벳 리스트에 포함된 문자일 때 빈깡통에 직전 글자와 함께 담아주도록 했다.

이때 만약 직전문자가 알파벳이 아닐경우에는 pass 해주도록해서 문자만 두글자씩 묶이도록 만들었다.

 

그렇게해서 만든 리스트1과 리스트2를 가지고 리스트1에 담긴 원소가 리스트2에도 있을 경우에 교집합 깡통에 그 원소를 담도록해서 교집합 리스트를 만들었고, 합집합은 두 리스트를 더 한 것에서 교집합을 빼주는 식으로 만들었다.

 

이후에 두 리스트가 같을 때는 바로 1이 나오도록 해주었고, 

아닐 경우에는 문제에서 제시한대로 자카드 유사도(교집합/합집합)를 구해 65536을 곱해주었다. 

 

이 방법으로 문제에서 제시된 테스트 케이스는 모두 통과했지만, 정확도 테스트에서는 일부 문제(61.5점; 5개/13개)를 실패했다. 어떤 부분이 틀렸을지 다시 한 번 생각해봐야겠다.

 

def solution(str1, str2):
    alp = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    str1, str2 = str1.lower(), str2.lower()
    
    list1, list2 = [], []
    
    num1, num2 = len(str1), len(str2)
    
    answer = 0
    
    for i in range(1,num1):
        if str1[i] in alp:
            if str1[i-1] not in alp:
                pass
            else:
                list1.append(str1[i-1]+str1[i])
     
    for i in range(1,num2):
        if str2[i] in alp:
            if str2[i-1] not in alp:
                pass
            else:    
                list2.append(str2[i-1]+str2[i])
    
    inter = []
    union = list1 + list2
    
    for i in list1:
        if i in list2:
            inter.append(i)
    
    for i in inter:
        union.remove(i)
    
    if list1 == list2:
        return 1 * 65536
    else:
        answer = len(inter)/len(union)
        return int(answer * 65536)