[c++/프로그래머스] 뉴스 클러스터링

문제 링크

뉴스 클러스터링

풀이

multiset으로 푼 문제

1. 먼저 비교를 위해 문자열을 나누어 multiset에 넣어주어야 한다.
   1-1. toupper로 대문자로 모두 변환 후, 영문자일 경우에만 ms에 넣어준다.
2. str1과 str2를 모두 나누어 multiset에 넣어줬으면 이제 비교를 한다.
   2-1. 그냥 set이 아닌 multiset을 사용하는 이유는 중복 원소 처리를 위함이다.
   2-2. ms1을 돌리면서 ms2에서 찾을 수 있으면 그 원소를 지워주는데(교집합 처리를 위해),
   그냥 erase로 지워주면 그 값을 가진 원소들이 모두 사라지기 때문에 iterator를 통해 지워줘야 한다.
   2-3. 지우면서 교집합 개수를 세기 위해 cnt++를 해준다.
3. 교집합의 개수는 2번에서 구한 cnt 값이 될 것이고, 합집합의 개수는 ms1과 ms2의 사이즈 합이 될 것이다. (이걸 위해 2-2를 한 것임)
4. 교집합과 합집합이 모두 0이라는 반례만 처리 해주면 answer는 (inter/uni)*65536값이 될 것이다.

   집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

코드

#include <string>
#include <iostream>
#include <set>

using namespace std;

multiset<string> seperate(string str) { // 문자열 나누기
    multiset<string> ms;
    for(int i=0;i<str.size();i++) { // 대문자 변환
        str[i] = toupper(str[i]);
    }
    for(int i=0;i<str.size()-1;i++) {
        string tmp = "";
        if('A'>str[i] || str[i]>'Z') continue; // 영문자가 아닌 것들 버리기
        if('A'>str[i+1] || str[i+1]>'Z') continue;
        tmp += str[i];
        tmp += str[i+1];
        ms.insert(tmp);
    }
    return ms;
}

int compare(multiset<string> &ms1, multiset<string> &ms2) {
    int cnt = 0;
    for(auto u : ms1) {
        if(ms2.find(u) == ms2.end()) continue; // ms1에 있는 값이 ms2에 없다면
        // ms2.erase(u); // 이거는 여러개를 지워버림
        auto it = ms2.find(u);
        ms2.erase(it);
        cnt++;
    }
    return cnt;
}

int solution(string str1, string str2) {
    int answer = 0;
    
    multiset<string> ms1 = seperate(str1);
    multiset<string> ms2 = seperate(str2);
    
    double inter = compare(ms1, ms2);
    double uni = ms1.size() + ms2.size();
    
    cout<<inter<<" "<<uni<<endl;
    if(inter == 0 && uni == 0) return 65536;
    answer = (inter/uni) * 65536;
    
    return answer;
}