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

풀이)

unordered_map 을 사용해서 푼 문제이다.

풀이과정은 이러하다.

1. 문자열 str1과 str2 각자 2글자씩 잘라서 원소를 만든다.

   (이 때, 2글자 중 영문자가 아닌 숫자, 기호 등이 오면 그 경우는 넘어간다.

영문자는 대문자로 통일시켜놓는다.)

2. 만들어진 원소들을 key로 생각하고, map을 통해 다중집합내에 같은 원소가 몇 개 저장되는 지 알아둔다.

3. 문자열 str1의 원소들을 둘러보며, str2에서 만든 원소와 같을 경우 둘 중 원소의 개수가 적은 것은 교집합에 넣는다.

   그러면, 교집합의 수를 구할 수 있다.

합집합의 경우,

전체 원소의 수 - 교집합 원소의 수 = 합집합 원소 수 임을 이용해서, 합집합도 구할 수 있다.

코드)

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

char check(char ch){ // 소문자를 대문자로 바꾸고, 영문자 아닌건 return 1로 해줌
    if('A' <= ch && ch <= 'Z'){//영어 대문자
        return ch;
    }
    else if('a' <= ch && ch <= 'z'){//영어 소문자
        return ch - 32;
    }
    else{
        return '1';
    }
}

int solution(string str1, string str2) {
    int answer = 0;
    unordered_map <string,int> vec1, vec2;
    vector <string> list1;
    int whole =0; //전체 원소 합 저장하는 변수
    //다중집합의 원소만듬
    string s = "";
    for(int i=0;i<str1.size()-1;i++){
        s ="";
        str1[i] = check(str1[i]);
        if(str1[i] == '1')continue;
        str1[i+1] = check(str1[i+1]);
        if(str1[i+1] == '1'){
            i++;
            continue;
        }
        s += str1[i];
        s += str1[i+1];
        whole++;// 전체집합 수 증가
       if(vec1.find(s) != vec1.end()){
           vec1[s]++;
       }
        else{
            vec1[s] = 1;
            list1.push_back(s);
        }
    }
   for(int i=0;i<str2.size()-1;i++){
        s ="";
        str2[i] = check(str2[i]);
        if(str2[i] == '1')continue;
        str2[i+1] = check(str2[i+1]);
        if(str2[i+1] == '1'){
            i++;
            continue;
        }
        s += str2[i];
        s += str2[i+1];
       whole++;
       if(vec2.find(s) != vec2.end()){
           vec2[s]++;
       }
        else{
            vec2[s] = 1;
        }
    }
    if(vec1.empty() && vec2.empty()) return 65536; // 만약 둘다 공집합이면 바로 return
   
    int hop=0, cardi=0; // 합집합의 수와 교집합의 수를 저장하는 변수
    //두 다중집합의 합집합수와, 교집합수 찾아냄
    for(int i=0;i<list1.size();i++){
        if(vec2.find(list1[i]) != vec2.end()){//같은 원소가 있을경우
            if(vec2[list1[i]] > vec1[list1[i]]){
                cardi += vec1[list1[i]]; //교집합의 경우 같은 원소면 두 집합 중 원소개수가 min인 값으로 교집합에 넣어줌
            } 
            else{
                cardi += vec2[list1[i]]; 
            } 
        }
    }
    hop = whole - cardi; // 합집합 = 전제집합 - 교집합
    float result = (float)cardi/(float)hop * 65536;//자키드 유사도 = 교집합/합집합
    answer = result;
    return answer;
}