[LV2] 뉴스 클러스터링

1. 문제

1) 문제 링크

    : https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

2) 설명

자카드 유사도를 활용해 두 문자열의 유사도를 비교하는 문제다

자카드 유사도에 대한 자세한 설명은 문제 링크에 있다

 

2. 풀이

1) 알고리즘

    : 집합?

 

2) 풀이 설명

C++로 sstream 사용해서 풀어도 되긴 하는데 파이썬으로 풀기에 너무 적합한 문제 같아서 그냥 파이썬으로 풀어봤다.

일단 소문자 대문자를 가리지 않기 때문에 문자열을 다 소문자로 변환했다.

그리고 각 문자열을 두 글자씩 떼서 리스트를 만든다. 이때 특수문자가 포함되어 있으면 건너뛴다.

이제 n(교집합) / n(합집합) 을 구하면 된다.(마지막에 한 번만 곱해주면 되기 때문에 65536을 곱하는 건 일단 생략하겠다...)

n(A U B) = n(A) + n(B) - n(A ^ B) // n(A ^ B)는 A B 교집합

공식을 이용한다.

교집합을 구하는 건 str1_arr(str1에서 두 글자씩 떼어낸 문자열 집합)에 있는 문자열 중 str2_arr(str2에서 두 글자씩 떼어낸 문자열 집합)에 있는 것들만 카운팅해준다. 카운팅하면 str2_arr에서 그 문자열은 빼줘야 한다. 왜냐하면 다음과 같은 경우를 방지하기 위해서다.

str1_arr = {1, 1, 1}

str2_arr = {1, 2, 3}

일 때 처음 1을 카운팅해주고 str2_arr에서 빼주지 않으면 두 번째, 세 번째 1에서도 str2_arr에 1 값이 있기 때문에 교집합의 개수가 3이 되기 때문이다.

 

여튼 그렇게 교집합의 개수를 구했으면 공식 따라서 자카드 유사도를 구해주면 된다.

 

 

3. 코드

def solution(str1, str2):
    mul_val = 65536
    
    # 소문자 변환
    str1 = str1.lower()
    str2 = str2.lower()
    
    # 두글자씩 떼어서 배열로 변환
    str1_arr = [ str1[i : i + 2] for i in range(len(str1) - 1) if str1[i : i + 2].isalpha() ]
    str2_arr = [ str2[i : i + 2] for i in range(len(str2) - 1) if str2[i : i + 2].isalpha() ]
    
    union_count = len(str1_arr) + len(str2_arr) # (A U B) = (A) + (B) - (A ^ B) 공식 사용 : 교집합 개수 구한 후 빼줘야 함
    # 교집합 개수 구하기
    intersection_count = 0
    for x in str1_arr:
        if x in str2_arr:
            intersection_count += 1
            str2_arr.remove(x)
    
    # 합집합 개수 구하기
    union_count -= intersection_count # 교집합 개수 빼주기
    
    if union_count == 0:
        return mul_val
    else:
        return int(intersection_count / union_count * mul_val)

 

 

4. 느낀점

리스트 컴프리헨션 최고!

문자열에 isalpha()라는 함수가 있다는 걸 처음 알았다..

Counter라는 걸 사용하면 교집합 합집합을 더 쉽게 구할 수 있는 것  같다. 틈 나면 공부해보자!(보통 이러면 안 한다)