[프로그래머스 Lv2] 뉴스 클러스터링

[구현 환경]

• C++

[문제 설명]

• string str1, string str2를 입력받아 자카드 유사도를 반환하는 문제
• 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중 하나
• 입력으로 들어온 str1과 str2를 두 글자씩 끊어서 다중집합의 원소로 만든 후, (교집합의 원소 수 / 합집합의 원소 수) * 65536을 return
• 만약 합집합과 교집합의 수가 0인 경우(다중 집합의 원소의 수가 모두 0인 경우) 65536을 return

[함수 원형]

int solution(string str1, string str2)
{
	int answer;
    
	return answer;
}

[풀이]

#include <iostream>
#include <string>
#include <algorithm>

int solution(string str1, string str2) {
    
    double answer = 0.0;

    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);

    auto checkOnlyAlphabet = [=](string text)
    {
        for (auto t : text)
        {
            if (t < 97 || t > 122) return false;
        }
        return true;
    };


    vector<string> jaccard1;
    for (int i = 1; i < str1.length(); ++i)
    {
        string str ="";

        str += str1[i - 1];
        str += str1[i];

        if(checkOnlyAlphabet(str))
            jaccard1.emplace_back(str);
    }

    vector<string> jaccard2;
    for (int i = 1; i < str2.length(); ++i)
    {
        string str = "";

        str += str2[i - 1];
        str += str2[i];
        
        if (checkOnlyAlphabet(str))
            jaccard2.emplace_back(str);
    }

    sort(jaccard1.begin(), jaccard1.end());
    sort(jaccard2.begin(), jaccard2.end());

    vector<string> unionJaccard(jaccard1.size() + jaccard2.size());
    auto iter = set_union(jaccard1.begin(), jaccard1.end(), 
				jaccard2.begin(), jaccard2.end(), unionJaccard.begin());
    unionJaccard.erase(iter, unionJaccard.end());

    vector<string> intersectionJaccard(jaccard1.size() + jaccard2.size());
    iter = set_intersection(jaccard1.begin(), jaccard1.end(), 
			jaccard2.begin(), jaccard2.end(), intersectionJaccard.begin());
    intersectionJaccard.erase(iter, intersectionJaccard.end());

    if (intersectionJaccard.size() == 0 && unionJaccard.size() == 0) return 65536;
    
    answer = double(intersectionJaccard.size()) / double(unionJaccard.size());    

    return floor(answer * 65536);
}

• 원할한 비교를 위해 모두 소문자로 transform
• 두 글자씩 끊어서 다중집합의 원소를 생성 => 소문자 범위 내에 포함되지 않으면 다중집합에 포함하지 않도록 람다함수 구현
• 다중집합을 정렬한 이후 set_union , set_intersection 함수를 이용해 합집합과 교집합을 구함
• 모두 0인 경우에 대한 예외처리 이후 문제의 수식에 맞게 return