2018 KAKAO BLIND RECRUITMENT[1차] 뉴스 클러스터링

programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

직관적으로 풀면 되고

다만 주의 할 점은

RA, RA, RB 와 같은 경우에

첫번째 RA에 대해서 교집합과 합집합에 대해 계산 했으면 두번째 RA는 사용되지 말아야 하므로

bool 처리를 해줘야 함.

 

#include<iostream>
#include <string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;

map<string, int> temp_a;
map<string, int> temp_b;
map<string, bool> common;


int solution(string str1, string str2) {

    

    for (int i = 0; i < str1.size(); i++)
    {
        if (str1[i] >= 'A' && str1[i] <= 'Z')
        {
            str1[i] -= 'A' - 'a';
        }
    }

    for (int i = 0; i < str2.size(); i++)
    {
        if (str2[i] >= 'A' && str2[i] <= 'Z')
        {
            str2[i] -= 'A' - 'a';
        }
    }

    vector<string> str_a;
    vector<string> str_b;

    for (int i = 0; i < str1.size() - 1; i++)
    {
        string temp = "";
        if (!(str1[i] >= 'a' && str1[i] <= 'z' && str1[i + 1] >= 'a' && str1[i + 1] <= 'z'))
        {
            continue;
        }
        temp += str1[i];
        temp += str1[i + 1];
        str_a.push_back(temp);
    }

    for (int i = 0; i < str2.size() - 1; i++)
    {
        if (!(str2[i] >= 'a' && str2[i] <= 'z' && str2[i + 1] >= 'a' && str2[i + 1] <= 'z'))
        {
            continue;
        }
        string temp = "";
        temp += str2[i];
        temp += str2[i + 1];
        str_b.push_back(temp);
    }

   

    for (int i = 0; i < str_a.size(); i++)
    {
        temp_a[str_a[i]]++;
    }
    for (int i = 0; i < str_b.size(); i++)
    {
        temp_b[str_b[i]]++;
    }

    int andn = 0;
    int sumn = 0;
    
    
    for (int i = 0; i < str_a.size(); i++)
    {
        if (temp_a[str_a[i]] && temp_b[str_a[i]] && !common[str_a[i]])
        {
            common[str_a[i]] = true;
            andn += min(temp_a[str_a[i]], temp_b[str_a[i]]);
            sumn += max(temp_a[str_a[i]], temp_b[str_a[i]]);
        }

        if (temp_a[str_a[i]] && !temp_b[str_a[i]] && !common[str_a[i]])
        {
            common[str_a[i]] = true;
            sumn += temp_a[str_a[i]];
        }
    }

    for (int i = 0; i < str_b.size(); i++)
    {
        
        if (temp_b[str_b[i]] && !temp_a[str_b[i]] && !common[str_b[i]])
        {
             common[str_b[i]] = true;
            sumn += temp_b[str_b[i]];
        }
    }
    
     if ((!str_a.size() && !str_b.size()) || !sumn)
    {
        return 65536;
    }

    int answer = 0;


    double ans = (double)andn / (double)sumn;
    answer = ans * 65536;
    return answer;
}