코딩테스트 문제 (16) - 뉴스 클러스터링

카카오 2018 블라인드 코딩테스트 문제입니다.

문제

문제는 입력으로 들어오는 두 문자열에 대해 자카드 유사도 (Jaccard Similaraity)를 계산하는 문제입니다.

1. str1 = 'FRANCE', str2 = 'french' => 16384
2. str1 = 'handshake', str2 = 'shake hands' => 65536
3. str1 = 'aa1+aa2', str2 = 'AAAA12' => 43690
4. str1 = 'E=M*C^2', str2 = 'e=m*c^2' => 65536

 

풀이

먼저, 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 집합 $A,B$에 대해서 $J(A,B) = INTERSECTION(A,B) / UNION(A,B)$ 로 정의됩니다. 각 집합의 원소가 중복된 다중집합에 대해서도 적용될 수 있습니다. 예를 들어, 집합 $A$는 원소 1을 3개 가지고 있고 집합 $B$는 원소 1을 5개 가지고 있다면 교집합은 min(3,5)인 3, 합집합은 max(3,5)인 5만큼 원소 1을 가지게 됩니다.

풀이는 생각보다 간단합니다. 문자열에 대해 전처리를 수행하고 collections 모듈의 Counter를 이용해 교집합, 합집합을 수행하면 될 것 같습니다.

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 자카드 유사도
• Counter 교집합, 합집합