[1차] 뉴스 클러스터링 (feat. 프로그래머스, 17677번)

[1차] 뉴스 클러스터링
https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

반응형

// woohyeon.kim
// https://school.programmers.co.kr/learn/courses/30/lessons/17677
#include <string>
#include <map>
using namespace std;
int solution(string str1, string str2) {
    for (int i = 0; i < str1.size(); ++i)
        str1[i] = toupper(str1[i]);
    for (int i = 0; i < str2.size(); ++i)
        str2[i] = toupper(str2[i]);
    map<string, int> str1_store, str2_store;
    for (int i = 0; i < str1.size() - 1; ++i)
        if ('A' <= str1.at(i) && str1.at(i) <= 'Z' && 'A' <= str1.at(i + 1) && str1.at(i + 1) <= 'Z')
            ++str1_store[to_string(str1.at(i)) + to_string(str1.at(i + 1))];
    for (int i = 0; i < str2.size() - 1; ++i)
        if ('A' <= str2.at(i) && str2.at(i) <= 'Z' && 'A' <= str2.at(i + 1) && str2.at(i + 1) <= 'Z')
            ++str2_store[to_string(str2.at(i)) + to_string(str2.at(i + 1))];

    int intersection_set = 0, sum_set = 0;
    for (auto iter = str1_store.begin(); iter != str1_store.end(); ++iter) {
        auto find_iter = str2_store.find(iter->first);
        if (find_iter != str2_store.end()) {
            auto& count_str1_store = iter->second;
            auto& count_str2_store = find_iter->second;
            intersection_set += min(count_str1_store, count_str2_store), sum_set += max(count_str1_store, count_str2_store);
        }
        else
            sum_set += iter->second;
    }
    for (auto iter = str2_store.begin(); iter != str2_store.end(); ++iter)
        if (str1_store.find(iter->first) == str1_store.end())
            sum_set += iter->second;
    auto jaccard_similarity = 0.0;
    if (sum_set == 0)
        jaccard_similarity = 1;
    else
        jaccard_similarity = static_cast<double>(intersection_set) / sum_set;
    return static_cast<int>(jaccard_similarity * 65536);
}
// *&)*@*

1. str1과 str2를 두개의 문자로 검사하여 각각 문자가 몇번 나왔는지를 검사합니다.
2. str1 기준으로 str2를 검사하며 min, max를 구하고 이를 교집합, 합집합 개수에 적용합니다.
3. str2 기준으로 str1을 검사합니다. str1에 같은 문자가 있다면 위 2번에 의해 계산됐을 것이므로 아닌 경우에만 합집합에 포함시킵니다.