카카오 1차 코딩테스트 5번 뉴스 클러스터링 문제풀이

카카오 1차 코딩 테스트 5번 문제풀이

문제 및 해설 바로가기

5. 뉴스 클러스터링(난이도: 중)

str1	str2	answer
FRANCE	french	16384
handshake	shake hands	65536
aa1+aa2	AAAA12	43690
E=M*C^2	e=m*c^2	65536

C++ 소스코드

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

void LowerString(string& str)
{
	for (int i = 0; i < str.length(); i++)
		str[i] = tolower(str[i]);
}

bool FilterChar(string& str)
{
    for (int i = 0; i < str.length(); i++)
        if (str[i] < 'a' || str[i] > 'z') 
            return false;
    return true;
}

vector<string> DivideString(string& str)
{
    vector<string> strVec;
    for (int i = 0; i < str.length() - 1; i++)
    {
        string temp = str.substr(i, 2);
        if (FilterChar(temp))
            strVec.push_back(temp);
    }
    return strVec;
}

int solution(string str1, string str2) {
    int result = 65536;
    
    LowerString(str1);
	LowerString(str2);

    vector<string> vStr1 = DivideString(str1);
    vector<string> vStr2 = DivideString(str2);

    int totalCount = vStr1.size() + vStr2.size();
    if(totalCount == 0)
        return result;
    
    sort(vStr1.begin(), vStr1.end());
    sort(vStr2.begin(), vStr2.end());

    vector<string> inter(totalCount);
    auto it = set_intersection(vStr1.begin(), vStr1.end(), vStr2.begin(), vStr2.end(), inter.begin());
    inter.erase(it, inter.end());
    
    int sameCount = inter.size();
    if (sameCount == 0)
        return 0;
    
    int unionCount = totalCount - sameCount;
    if (unionCount == 0)
        return result;

    return (float)sameCount / unionCount * result;
}

void main()
{
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);

    cout << solution(str1, str2);
}