- Date : 2020.10.16(금)
- Time : 60분
- 유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 자카드 유사도라는 방법을 찾아냈다.
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 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 ∩ 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가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {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가 된다. 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
list1 = [str1[n:n+2].lower() for n in range(len(str1)-1) if str1[n:n+2].isalpha()]: 먼저 다중집합의 원소를 만들어야한다. 2개씩 끊고 모든 영어의 대문자는 소문자로 만든다. 여기서 숫자,공백,특수문자 등은 if 문으로 거를 수 있다. isalpha()를 통해 영어 문자인 경우만 list1에 들어가게 된다.
tlist = set(list1) | set(list2)
if tlist:
for i in tlist:
res1.extend([i]*max(list1.count(i), list2.count(i)))
res2.extend([i]*min(list1.count(i), list2.count(i)))
answer = int(float(len(res2)) / float(len(res1)) * 65536)
return answer
else:
return 65536: tlist는 중복을 제거한 합집합의 모임이다. |로 합집합을 구할 수 있는데 set 형태임으로 중복이 걸러진다. 하지만 문제에서는 중복을 허용하는 다중집합에 대해서 확장할 수 있기 때문에 중복을 다시 더해주는 과정이 필요했다. 그래서 겹치는 원소의 최대 카운트 수를 더한건 최종 합집합으로 겹치는 원소의 최소 카운트를 더한건 최종 교집합으로 넘어가게된다. 중복처리를 하는게 까다로웠다..ㅠㅠ