C++:: 프로그래머스 < [1차] 뉴스 클러스터링 >

구구절절 이상한 얘기를 하다가 결국에는 자카드 유사도를 구하라는 문제이다. 쉽게 말하면 자카드 유사도는 두 다중집합에서 교집합의 개수/ 합집합의 개수 를 의미한다. 교집합과 합집합이 둘다 0일때의 예외처리를 해주고 리턴해주면 되는 간단한 문제이다.

#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;

void getElements(string str, unordered_map<string, int>& um) {
    for (auto &c : str) c = tolower(c);// 대소문자 가리지 않으므로 소문자로
    for (int i=0; i<str.size()-1; i++) {
        if (!isalpha(str[i]) || !isalpha(str[i+1])) continue ;// 알파벳이 아니라면 넘긴다.
        um[str.substr(i, 2)]++;// 데이터 저장
    }
}

int solution(string str1, string str2) {
    int inter_str = 0, union_str = 0;
    unordered_map<string, int> um_str1, um_str2;
    getElements(str1, um_str1);
    getElements(str2, um_str2);
    
    for (auto element : um_str1) {// 교집합
        if (um_str2[element.first]) {// 다른 집합에 존재한다면
            inter_str += min(element.second, um_str2[element.first]);// 교집합 개수 ++
            // map은 참조하여 없는 값이면 0으로 값이 설정되므로 이점을 유의하여야 한다.
            um_str2[element.first] = max(element.second, um_str2[element.first]);// 곂치는 원소면 최대 개수
        }
        else {
            um_str2[element.first] = element.second;// 원소 개수 등록
        }
    }
    // 위에서 um_str1을 판별하면서 um_str2를 합집합으로 만들어 놓았기에 그대로 안에값을 더해주기만 하면 됨
    for (auto element : um_str2) {// 합집합
        union_str += element.second;
    }
    if (!union_str) return 65536;// 예외처리
    return floor(inter_str*65536/union_str);
}