[프로그래머스] Level 2. 뉴스 클러스터링

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

해결방법

1. str1을 이용해 집합을 구한다 (a)
2. str2을 이용해 집합을 구한다 (b)
3. a집합의 개수 와 b집합의 개수를 구한다. 그리고 a집합과 b집합의 교집합 개수를 구한다.
4. 합집합 개수는 a집합개수 + b집합개수 - 교집합개수이다.
5. J를 구해 반환한다.

문제에서 하라는 대로 하면 되는데, 몇 가지 주의사항만 지키면 된다.

• 'ab' , 'AB', 'aB','Ab' 는 모두 동일한 원소로 취급된다. 따라서 모두 소문자로 변환한 후에 집합에 넣어야 한다. (혹은 모두 대문자로)
• 'abab'일 경우 'ab' 가 2개 나온다. 이때 집합의 총 수는 'ab','ba','ab'로 총 3개이다. 따라서 map을 사용해 'ab'가 2개, 'ba' 가 1개 와 같은 형식으로 저장해야 한다. 
• 교집합의 개수를 찾을 때, a의 for문을 돌면서 b에도 해당원소가 있는지 검사한다. 만약 a에서 'ab'가 2개, b에서 'ab' 가 한개라면 이 겹치는 수는 1개이다. 따라서 최솟값을 찾아야한다.

 

#include <string>
#include <map>
#include <cctype>
#include <cmath>
#include <iostream>


using namespace std;

map<string,int> a; map<string,int> b;

void make_set(string str, map<string,int>& m){
    for(int i=0; i<str.size()-1; i++){
        if(!isalpha(str[i]) || !isalpha(str[i+1])) continue;
        string result;
        result += tolower(str[i]);
        result += tolower(str[i+1]);
        
        if(m.find(result) == m.end())m.insert({result,1});
        else m[result] +=1;
    }
}

float funcJ(){
    
    int acnt = 0; int bcnt = 0;
    int andcnt = 0;
    for(auto it : a){
        acnt += it.second;
        
        if(b.find(it.first) != b.end()){ //b도 가지고있다면 둘중 작은수를 addcnt에 넣어줌. 교집합개수
            andcnt += min(b[it.first], it.second);
        }
    }
    
    for(auto it:b){bcnt += it.second;} //b 총개수
    
    int orcnt = acnt + bcnt - andcnt;
    return orcnt == 0 ? 1 : 1.0f * andcnt / orcnt;
}

int solution(string str1, string str2) {
    
    make_set(str1, a);
    make_set(str2, b);
    
    return static_cast<int>(floor(funcJ() * 65536));
}