ニュースクラスタ

Description

多くのメディアが次々と報道しているニュース、特に速報ニュースは、似たような見出しのニュースが多いため、本当に必要なニュースを見つけるのは難しい.ダウムニュースの開発を担当する新入社員のTubeは、問題の改善を担当し、ユーザーがさまざまなニュースを閲覧しやすいようにしています.
開発方向を決めるため、Tubeはまず最近話題になっているKACAの新人開発者の公募に関する記事を検索した.
「Kakao初の公募…」ブラインド方式
Kakaoが合併して初めて公募...ブラインド開発者の採用
KACA、BLINDを代表とする新規開発者の公募
ココア公債、新開発者のコード能力だけ見て
Kakao~新公募...コーディング能力だけ見て
Kakaoコード能力により、2018新開発者を選抜
記事のテーマを基準として,ブラインド文に注目する典型的な記事と符号化テストに注目する記事に分けられることが分かった.Tubeは、これらの人たちを別々に組み合わせて展示すれば、KACAの公開求人に関する記事を探しているユーザーにとって役立つと考えている.
似たような記事の基準を決めるために、論文や資料を調べたTubeは「花の類似度」の方法を見つけた.
提花類似度は集合間の類似度を検証する様々な方法の一つであるという.2つの集合A,B間の花類似度J(A,B)は、2つの集合の交差サイズを2つの集合の和の集合サイズで割った値として定義される.
例えば、集合A={1,2,3}、集合B={2,3,4}の場合、交差A∏B={2,3}、集合A B={1,2,3,4}、集合A,B間の提花類似度J(A,B)=2/4=0.5となる.集合Aと集合Bが共に集合である場合、除算は定義されないので、それぞれJ(A,B)=1と定義される.
提花類似度は、要素の重複を許容する複数の集合を拡張することができる.複数セットAには3つの要素1があり、複数セットBには5つの要素1がある.この複数の集合の交差A∏Bは3つの元素1がmin(3,5)であり,集合A≡Bは5つの元素1がmax(3,5)である.複数の集合A={1,1,2,2,3}であり、複数の集合B={1,2,2,4,5}であり、交差A∏B={1,2,2,2,2,3,4,5}であるため、提花類似度J(A,B)=3/7、約0.42である.
文字列間の類似度の計算に使用できます.文字列FRANCEとFRENCHが与えられると、2文字を切り離して複数のセットを作成できます.それぞれ{FR,RA,AN,NC,CE},{FR,RE,EN,NC,CH}であり,交差は{FR,NC}であり,{FR,RA,AN,NC,CE,RE,EN,CH}であり,両文字列間の文字類似度J("FRANCE","FRENCH")=2/8=0.25である.

Input

入力はstr 1とstr 2の2つの文字列です.各文字列の長さは2以上、1000以下です.
入力入力として入力された文字列は2つの文字を遮断され、複数の集合の要素となる.この場合、アルファベット文字ペアのみが有効で、他のスペースまたは数値、特殊文字が含まれている場合は、その文字ペアが破棄されます.たとえば、「ab+」が入力として使用される場合、「ab」のみが複数のセットの要素として使用され、「b+」は破棄されます.
複数の集合要素間で比較する場合、大文字と小文字の区別は無視されます.「AB」と「AB」、「ab」は同じ元素である.

Output

入力した2つの文字列の花の類似度を出力します.類似度値は0から1までの実数であり、処理を容易にするために65536に小数点以下を乗じて整数部のみ出力する.

Example

str1 : "FRANCE"& str2 : "french"-> 16384
str1 : "handshake"& str2 : "shake hands" -> 65536
str1 : "aa1+aa2"& str2 : "AAAA12" -> 43690
str1 : "E=MC^2" & str2 : "e=mc^2" -> 65536

Code

#include <bits/stdc++.h>

using namespace std;

string util(string str){
    int l = str.length();
    string result = "";
    for (int i = 0; i <l ; i++)
    {
        if((int(str[i]) >= int('a') && int(str[i]) <= int('z')) || (int(str[i]) >= int('A') && int(str[i]) <= int('Z')))
            result += tolower(str[i]);
        else
            result += str[i];
    }
    return result;
}

bool check_valid(char c){
    
    if((int(c) >= int('a') && int(c) <= int('z')) || (int(c) >= int('A') && int(c) <= int('Z')))
        return true;
    

    return false;
}

int solution(string str1, string str2) {
    int answer = 0;
    unordered_map<string, int> um_1;
    unordered_map<string, int> um_2;

    str1 = util(str1);
    
    str2 = util(str2);
    
    for(int i=0; i<str1.length()-1; i++){
        string tmp = "";
        if(check_valid(str1[i+1]) && check_valid(str1[i]))
            tmp += str1.substr(i,2);
        else
            continue;
        if(um_1[tmp])
            um_1[tmp] += 1;
        else
            um_1[tmp] = 1;
    }
        
    for(int i=0; i<str2.length()-1; i++){
        string tmp = "";
        if(check_valid(str2[i+1]) && check_valid(str2[i]))
            tmp += str2.substr(i,2);
        else
            continue;
        if(um_2[tmp])
            um_2[tmp] += 1;
        else
            um_2[tmp] = 1;
    }
    
    int sum = 0;
    int com = 0;
    
    for (auto p : um_1){
        if(um_2[p.first]){
            sum += max(um_2[p.first], p.second);
        }
        else{
            sum += p.second;
        }
    }
    for (auto p : um_2){
        if(!um_1[p.first])
            sum += p.second;
    }
    
    // get com
    for (auto p : um_1){
        if(um_2[p.first])
            com += min(um_2[p.first], p.second);
    }
    
    
    if (com == 0 && sum == 0)
        answer = 65536;
    else{
        double j = double(com)/double(sum);
        answer += int(j*65536);    
    }
    

    return answer;
}

Thoughts

2018年のKaKaoブラインド求人で初めて出た問題で、当時の難易度は中で、正解率は41.8%で、決して容易な問題ではありませんでした.
最初は目標時間が30分だったのですが、実際は45分くらいかかったようです.
問題はそれほど複雑ではないが,第一に紹介した概念「提花類似度」「複数集合」の説明を読み,把握することが核心である.
問題の解釈と理解にかかる時間は約5分で,その後どのような方法で構想したのか.
まずutilという関数を作成し、与えられたstringの大文字と小文字を小文字に統一します.
次いで,無秩序mapを用いて複数の集合を実現した.stringでは、validをチェックし、無秩序mapでk、vを使用してこれらの要素を複数のセットに追加する方法を使用し、交差する数とセットの数をチェックすることで、問題は難しくありません.
しかし最後の5分以内に少数の除法を行った場合、int間の除法が除かれるとintが返されるのでtype castingが必要になるとは見えないので少し時間がかかりましたが、この問題は数学的概念や問題で与えられた概念の理解などがあれば難しくありません.
時間が経つにつれて符号化テストのレベルは向上すると言われていますが、2年前の41%の正解率の問題がプログラマーlv 2のレベルであることからも、そうであるようです.