[Programmers] Lv2. 뉴스 클러스터링 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

중복이 가능한 원소들을 지니고 있어야 하므로, multiset을 사용하였습니다.

 

1. 주어진 문자열을 두 글짜씩 끊어, 다중집합 만들기

• 끊어서 만든 두 글자 중 하나라도 알파벳이 아니라면 다음 문자로 넘어간다.
• 두 글자 모두 알파벳이라면 다중집합에 원소 추가

#include <string>
#include <set>
using namespace std;

multiset<string> CreateMultipleSet(const string& str) {
    multiset<string> result;
    int strLength = str.length() - 1;
    int extractionNum = 2;

    for (int i = 0; i < strLength; i++) {
        string element;
        bool isDiscardSet = false;

        for (int j = i; j < i + extractionNum; j++) {
            if (!isalpha(str[j])) {
                isDiscardSet = true;
                break;
            }

            element.push_back(tolower(str[j]));
        }

        if (!isDiscardSet)
            result.insert(element);
    }

    return result;
}

 

2. 다중집합의 교집합, 합집합 구하기

• <algorithm>과 <iterator> 헤더에 있는 set_union(), set_intersection(), inserter()를 활용
  • inserter()에 대한 🔗참고 글
  • set_intersection(), set_union()에 대한 🔗참고 글

#include <string>
#include <iterator>
#include <algorithm>
#include <set>
using namespace std;

multiset<string> SetIntersection(const multiset<string>& set1, const multiset<string>& set2) {
    multiset<string> result;
    set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(result, result.begin()));
    return result;
}

multiset<string> SetUnion(const multiset<string>& set1, const multiset<string>& set2) {
    multiset<string> result;
    set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(result, result.begin()));
    return result;
}

 

3. 자카드 유사도 구하기

const int MULTIPLY = 65536;

int FindJaccardSimilarity(const multiset<string>& intersections, const multiset<string>& unions) {
    if (intersections.empty() and unions.empty())
        return 1 * MULTIPLY;
    return ((double)intersections.size() / unions.size()) * MULTIPLY;
}

 

✏️소스 코드 및 결과

#include <string>
#include <iterator>
#include <algorithm>
#include <set>
using namespace std;
const int MULTIPLY = 65536;
/* https://stackoverflow.com/questions/41782233/i-want-to-perform-a-multi-set-intersection-using-c */

multiset<string> CreateMultipleSet(const string& str) {
    multiset<string> result;
    int strLength = str.length() - 1;
    int extractionNum = 2;

    for (int i = 0; i < strLength; i++) {
        string element;
        bool isDiscardSet = false;

        for (int j = i; j < i + extractionNum; j++) {
            if (!isalpha(str[j])) {
                isDiscardSet = true;
                break;
            }

            element.push_back(tolower(str[j]));
        }

        if (!isDiscardSet)
            result.insert(element);
    }

    return result;
}

multiset<string> GetIntersection(const multiset<string>& set1, const multiset<string>& set2) {
    multiset<string> result;
    set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(result, result.begin()));
    return result;
}

multiset<string> GetUnion(const multiset<string>& set1, const multiset<string>& set2) {
    multiset<string> result;
    set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter(result, result.begin()));
    return result;
}

int FindJaccardSimilarity(const multiset<string>& intersections, const multiset<string>& unions) {
    if (intersections.empty() and unions.empty())
        return 1 * MULTIPLY;
    return ((double)intersections.size() / unions.size()) * MULTIPLY;
}

int solution(string str1, string str2) {
    multiset<string> multiSet1 = CreateMultipleSet(str1);
    multiset<string> multiSet2 = CreateMultipleSet(str2);
    
    auto intersections = GetIntersection(multiSet1, multiSet2);
    auto unions = GetUnion(multiSet1, multiSet2);
    int answer = FindJaccardSimilarity(intersections, unions);
    return answer;
}