[プログラマー]2018 KAKAO BLIND RECRUITMENT Lv 1[最初の]ニュースクラスタ

10717 ワード

programmers C テキストリンク

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

2つの文字列に対して花の類似度を求める問題.
私は提花流砂島自体に慣れていませんが、
問題は詳しく説明されているので,理解にかたくない.
前回プログラマーの問題をしたとき.
STLをうまく利用していなかったので思い出しました.
今回実施する前にぜひGoogleをプレイしてみてください!
C++でサポートされている関数は本当に多いようです.

学識

1.to string()を使用する場合はご注意ください

文字列の各文字を入力し、そのうちの1文字をto stringとして複数のセットの要素を作成します.
stringは生成されずintの結果値が得られる.

文字列を作成し、+=演算子を使用すると、intではなく文字列の結果が得られます.

2.交差、集合

<アルゴリズム>のset交差()とset union()を使用

ビット関数のベクトルは、使用前にsort()を行う必要があります.

// 교집합
vector<string> intersection(multiSet_A.size() + multiSet_B.size());
    auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
    intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기
// 합집합
vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
    auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
    multi_union.erase(iter_b, multi_union.end());

3.ベクトル重複要素除去

は複数の集合の交点ではなく,通常の交点では重複はできないため,重複解消が行われている.

「アルゴリズム」の唯一の()を使用しました.

unique()は、重複する要素をアレイの末尾に送信し、その末尾値を返す最初のインデックス

を返す.

したがって、erase()の最初のパラメータを使用すると、不要な要素

を除去することができる.

intersection.erase(unique(intersection.begin(), intersection.end()), intersection.end()); // 교집합 중복 제거

4.特定の要素の数を取得

「アルゴリズム」のcount()を使用しました.

の下のコードは少し複雑です.パラメータに叩くのはあまり好きではなかったのですが、
作成後、プログラマーから他の人のコードを参考にしたところ、1行減ったようで、そのまま

を修正しました.

count(v.begin()、v.end()、element):vの始終を検査することによって、要素の個数

を求める

for(iter = intersection.begin(); iter != intersection.end(); iter++)
    {
        counts_min[idx] = min(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
        counts_max[idx++] = max(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
    }

問題を整理する

実装する重要な機能の特定

1号は、異常処理で異なる点があります.どの文字について、スペース、数字、特殊文字に変更するかは、一つ一つチェックするよりもアルファベットのみチェックするように変更します

ここで交わりを求めるとき,複数の集合の交わりの概念は少し異なると思う.
通常の交差を作成し、複数の集合の交差を作成することを決定します.そうですね.
いいえ、しかし、私はここで愚かなことをしました.
問題が複数の集合の交差と和の集合を記述する場合.
交差の中で共通要素が最も少なく、集合の中で共通要素が最も多い.
これは実は交差と合集だけで、自然です.

ですので、この問題では、重複除外のために事実交差を作成する必要があります.
各複数の集合では、共通要素の個数を求めるためにcount関数を使用する必要はありません.
でもこの方式も順調...ああ、ライブラリを勉強しても、コードを整理したような気がします...

CODE

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


int solution(string str1, string str2) {
        vector<string> multiSet_A;
    vector<string> multiSet_B;

    vector<string> ::iterator iter;
    for(int i=0; i<str1.length()-1; i++)
    {
        string tmp;
        if(isalpha(str1[i]) && isalpha(str1[i+1]))
        {
            tmp += tolower(str1[i]);
            tmp += tolower(str1[i+1]);
            
            multiSet_A.push_back(tmp);
        }
    }

    for(int i=0; i<str2.length()-1; i++)
    {
        string tmp;
        if(isalpha(str2[i]) && isalpha(str2[i+1]))
        {
            tmp += tolower(str2[i]);
            tmp += tolower(str2[i+1]);
            multiSet_B.push_back(tmp);
        }
    }

    if(multiSet_A.size() == 0 && multiSet_B.size() == 0) // 다중집합 A, B가 모두 공집합인 경우 
    {
        return MUL;
    }

    sort(multiSet_A.begin(), multiSet_A.end());
    sort(multiSet_B.begin(), multiSet_B.end());

    vector<string> intersection(multiSet_A.size() + multiSet_B.size());
    auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
    intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기

    // 다중집합의 합집합
    vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
    auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
    multi_union.erase(iter_b, multi_union.end());

    int Jaccard = 0;

    Jaccard = ((float)intersection.size() / (float)multi_union.size()) * 65536;
    cout<<Jaccard<<endl;
    return Jaccard;
}

コード(バカバージョン...)

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


int solution(string str1, string str2) {
        vector<string> multiSet_A;
    vector<string> multiSet_B;

    vector<string> ::iterator iter;
    for(int i=0; i<str1.length()-1; i++)
    {
        string tmp;
        if(isalpha(str1[i]) && isalpha(str1[i+1]))
        {
            tmp += tolower(str1[i]);
            tmp += tolower(str1[i+1]);
            
            multiSet_A.push_back(tmp);
        }
    }

    for(int i=0; i<str2.length()-1; i++)
    {
        string tmp;
        if(isalpha(str2[i]) && isalpha(str2[i+1]))
        {
            tmp += tolower(str2[i]);
            tmp += tolower(str2[i+1]);
            multiSet_B.push_back(tmp);
        }
    }

    if(multiSet_A.size() == 0 && multiSet_B.size() == 0) // 다중집합 A, B가 모두 공집합인 경우 
    {
        return MUL;
    }

    sort(multiSet_A.begin(), multiSet_A.end());
    sort(multiSet_B.begin(), multiSet_B.end());

    // 일반 교집합
    vector<string> intersection(multiSet_A.size() + multiSet_B.size());
    auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
    intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기
    

//-----------------------이 부분이 전혀 필요가 없음-------------------------
    intersection.erase(unique(intersection.begin(), intersection.end()), intersection.end()); // 교집합 중복 제거
    // 교집합 내 원소의 최소/최대 개수
    int counts_min[intersection.size()];
    int counts_max[intersection.size()];
  
    int idx = 0;
    for(iter = intersection.begin(); iter != intersection.end(); iter++)
    {
        counts_min[idx] = min(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
        counts_max[idx++] = max(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
    }

    // 다중집합의 교집합
    vector<string> multi_intersection;
    idx = 0;
    for(iter = intersection.begin(); iter!= intersection.end(); iter++)
    {
        for(int i=0; i<counts_min[idx]; i++)
        {
            multi_intersection.push_back(*iter);
        }
        idx++;
    }
//-----------------------------------------------------------------------
    // 다중집합의 합집합
    vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
    auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
    multi_union.erase(iter_b, multi_union.end());

   // 자카드 유사도 계산
    int Jaccard = 0;

    Jaccard = ((float)multi_intersection.size() / (float)multi_union.size()) * 65536;
    
    return Jaccard;
}

Reference

この問題について([プログラマー]2018 KAKAO BLIND RECRUITMENT Lv 1[最初の]ニュースクラスタ), 我々は、より多くの情報をここで見つけました https://velog.io/@minjujuu/프로그래머스-2018-KAKAO-BLIND-RECRUITMENT-Lv1.1차-뉴스-클러스터링

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

Data Structureを整理してみましょう.//Part3

Weasley-モデリング