Level 2. 뉴스 클러스터링

11. 뉴스 클러스터링

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > 뉴스 클러스터링
https://programmers.co.kr/learn/courses/30/lessons/17677

---

문제 설명

Input value

• str1,str2 = 문자열

Process

• 문자열을 두 글자씩 끊어서 다중집합의 원소로 만든다.

  • 이 때, 영문자로 되어있는 글자 쌍만 유효하며, 기타 공백이나 숫자, 특수문자가 들어있는 경우는 그 쌍을 버린다.

• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다.

Output value

• 두 문자열의 자카드 유사도(J(A,B) = len(A∩B)/len(A∪B))를 구하고 65336을 곱한 뒤 소수점 아래를 버린 후 값을 return 한다.

• 두 문자열의 다중집합이 모두 공집합일 때 J(A,B) = 1로 정의한다.

---

문제 구상

set()을 이용하여 풀이하여 중복된 값을 추가하는 방법도 있지만, 해당 문제를 풀 당시 중복된 값을 어떻게 해결해야 할지 방도를 찾지 못해 list로 풀었다.

1. 두글자씩 묶으면서, isalpha()로 단어만 필터링 한 후, 소문자 처리를 수행하였다.

#01
str1 = [str1.lower()[i:i+2] for i in range(len(str1)-1) if str1.lower()[i:i+2].isalpha()]
str2 = [str2.lower()[i:i+2] for i in range(len(str2)-1) if str2.lower()[i:i+2].isalpha()]

2. 리스트 중 짧은 길이를 가지는 리스트를 기준으로 일치하는 값이 있으면 해당 값을 리스트에서 제거하고, 교집합 리스트에 추가했다.

if len(str1)>len(str2):
    inter = len([str1.remove(i) for i in str2 if i in str1])
else:
    inter = len([str2.remove(i) for i in str1 if i in str2])

3. $a∪b = a + b - a∩b$이므로 합집합은 다음과 같다.

union = len(str1)+len(str2)-inter

4. 합집합의 길이가 0 인 경우(= 두 문자열의 다중집합이 모두 공집합일 때 $J(A,B) = 1$로 정의한다.)의 조건에 맞추어 $65536$으로 지정하고, 아닐 경우 $J(A,B)*65536$을 return 하게 설정하였다.

answer = int(65536 if union == 0 else 65536*inter/union)

---

문제 풀이

def solution(str1,str2):
    str1 = [str1.lower()[i:i+2] for i in range(len(str1)-1) if str1.lower()[i:i+2].isalpha()]
    str2 = [str2.lower()[i:i+2] for i in range(len(str2)-1) if str2.lower()[i:i+2].isalpha()]
    if len(str1)>len(str2):
        inter = len([str1.remove(i) for i in str2 if i in str1])
    else:
        inter = len([str2.remove(i) for i in str1 if i in str2])
    union = len(str1)+len(str2)
    return int(65536 if union == 0 else 65536*inter/union)

---

마치며

해당 문제 출제의 의도는 중복되는 값이 있을 때, 교집합의 값을 구하는 방법을 찾는것이 아닌가 싶다. 코드를 압축하기 위해 입력값을 계속 수정하는 방법을 모색해봤지만 중복에 대한 영향을 고려할 수 없었으며..적당히 줄여야 한다. 는 것을 깨달았다.