[프로그래머스] 뉴스 클러스터링 문제풀이 c++

map을 이용해 문제를 풀었다.

문자열 str1, str2에 대해서

문자를 두글자씩 끊어서 다중집합의 원소로 만드는데,

알파벳 소문자일때는 toupper로 대문자로, 대문자는 그대로, 그외에는 무시하는 것으로 처리했다.

str1은 m1, str2는 m2에 다중집합의 원소를 저장하고 이때마다 합집합 uni값을 증가하였다.

m1을 탐색하여 m1의 first(string)에 해당하는 m2값이 존재한다면

m1의 second(int)과 m2값 중 min값을 교집합 inter값에 더하면 교집합의 수를 알 수 있다.

uni는 전체 원소의 개수이므로 여기서 교집합을 빼면 합집합의 수를 구할 수 있다.

uni와 inter가 둘 다 0이면 자카드 유사도는 1이고,

그 외엔 inter/uni이므로, 여기에 65536을 곱하면 answer를 구할 수 있다.

 

#include <string>
#include <map>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    int uni = 0, inter = 0;
    map<string,int> m1, m2;
    
    for(int i=0; i<str1.size()-1; i++){
        string s = "";
        if(str1[i]<='Z'&&str1[i]>='A'){
            s = str1[i];
        }
        else if(str1[i]<='z'&&str1[i]>='a'){
            s = toupper(str1[i]);
        }
        else{
            continue;
        }
        if(str1[i+1]<='Z'&&str1[i+1]>='A'){
            s += str1[i+1];
        }
        else if(str1[i+1]<='z'&&str1[i+1]>='a'){
            s += toupper(str1[i+1]);
        }
        else{
            continue;
        }
        m1[s]++;
        ++uni;
    }
    for(int i=0; i<str2.size()-1; i++){
        string s = "";
        if(str2[i]<='Z'&&str2[i]>='A'){
            s = str2[i];
        }
        else if(str2[i]<='z'&&str2[i]>='a'){
            s = toupper(str2[i]);
        }
        else{
            continue;
        }
        if(str2[i+1]<='Z'&&str2[i+1]>='A'){
            s += str2[i+1];
        }
        else if(str2[i+1]<='z'&&str2[i+1]>='a'){
            s += toupper(str2[i+1]);
        }
        else{
            continue;
        }
        m2[s]++;
        ++uni;
    }
    for(auto it=m1.begin(); it!=m1.end(); it++){
        if(m2.find(it->first) != m2.end()){
            inter += min(m2[it->first], it->second);
        }
    }
    uni -= inter;
    if(uni == 0 && inter == 0){
        answer = 65536;
    }
    else{
        answer = 65536*inter/uni;
    }
    return answer;
}