🤔문제 해석
자카드 유사도는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의한다.
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 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가 된다.
❗ 입출력 형식
입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
😏풀이
먼저 str1, str2을 모두 소문자로 바꿔준다.
반복문을 이용하여 연속으로 두 자리 모두 소문자인 경우 잘라서 s1과 s2에 넣어준다.
자카드 유사도의 정의에 따라 s1과 s2 모두 비어있을 땐 65536 그대로 출력한다.
교집합을 찾기 위해 s1과 s2의 크기에 따라 작은 vector의 원소들을 큰 vector의 원소들과 비교하며 같은 것이 있을 경우 min값을 늘려주며 교집합의 수를 저장한다.
합집합의 크기는 두 집합의 크기를 더한 뒤 교집합의 크기를 빼준 값이다.
자카드 유사도를 구한 뒤 출력 형식에 맞추어 출력한다.
💻코드
#include <string>
#include <algorithm>
using namespace std;
int solution(string str1, string str2) {
int answer = 0, min = 0, max = 0;
vector<string> s1, s2, words;
transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
for(int i = 0; i < str1.size() - 1; i++)
{
string tmp = str1.substr(i, 2);
if(tmp[0] >= 'a' && tmp[0] <= 'z' && tmp[1] >= 'a' && tmp[1] <= 'z')
s1.push_back(tmp);
}
for(int i = 0; i < str2.size() - 1; i++)
{
string tmp = str2.substr(i, 2);
if(tmp[0] >= 'a' && tmp[0] <= 'z' && tmp[1] >= 'a' && tmp[1] <= 'z')
s2.push_back(tmp);
}
if(s1.empty() && s2.empty())
return 65536;
max = s1.size() + s2.size();
if(s1.size() > s2.size())
{
for(int i = 0; i < s2.size(); i++)
{
auto itr = find(s1.begin(), s1.end(), s2[i]);
if(itr != s1.end())
{
min++;
s1.erase(itr);
}
}
}
else
{
for(int i = 0; i < s1.size(); i++)
{
auto itr = find(s2.begin(), s2.end(), s1[i]);
if(itr != s2.end())
{
min++;
s2.erase(itr);
}
}
}
max -= min;
if(max == 0)
return 65536;
double tmp = (double)min / (double)max;
return tmp * 65536;
}