[アルゴリズム解答分析]プログラマー不良ユーザー(2019 KaKao冬季実習)

今日解いた2番目の問題はプログラム不良ユーザーです.とても悲しくて、、、、もとはすぐにもっと良く解けることができて、しかし帰ってくるのがとても长い时间を使って、ううう、考えすぎるのが难しいこともあって、ふだん使う関数に対してとても良い理解がなくて、、、!試験前に知っていたことは何ですか.大丈夫、、、!😭😭😭

プログラム不良ユーザー

開発チーム内で開発活動を担当していた「無知」は、最近行われたカカの表情活動で異常な方法で当選しようとした応募者を発見した.これらの応募者を収集し、不良ユーザーの名義でリストをリストし、当選者代表の「専門家」に転送し、当選処理時に排除します.プライバシーを保護するために、ユーザーの特定のアイデンティティを「」文字で隠し、送信します.1文字に1つの「」文字が使用され、各IDには少なくとも1つの「*」文字が使用されます.
「無知」と「専門家」は、不良ユーザーのリストに映った応募者IDを題材IDと呼ぶことにした.
たとえば、イベントに対して次の完全なユーザーIDリストが指定されている場合:
応募者ID frodofradicrodobabc 123 frodoc
不良ユーザーIDリストがある場合は、次の操作を行います.
不良ユーザーfrdabc 1**
次の2つの場合、不良ユーザーにマッピングし、当選から除外するトピックIDリストが必要になる場合があります.
題材id frodoadabc 123
題材IDフラディアック123
アクティブ応募者IDリスト付きの配列user idと不良ユーザIDリストを含む配列無効idをパラメータとする場合、solution関数を完了し、当選中の題材IDリストを除外するためにいくつかの場合に発生する可能性のある数を返します.

にゅうしゅつりょく

user id配列のサイズは8を超えない.

user id配列の各要素の値は、1または8未満の長さの文字列です.

登録ユーザーのIDは重複しません.

のユーザIDは、小文字と数字で構成される.

で無効になっているid配列のサイズはuser id配列のサイズ以下です.

で無効になっているid配列の各要素の値は、1または8未満の長さの文字列です.

不良ユーザIDには、アルファベット小文字、数字、およびマスキング用文字「*」のみが含まれます.

不良ユーザIDには、1つ以上の"*"文字が含まれています.

の1つの不良ユーザIDは1つの応募者IDに相当し、同じ応募者IDを繰り返して制裁IDリストに入ることはない.

トピックのIDリストを取得した場合、これらのIDの順序にかかわらず、IDリストの内容が同じであれば、それを同一と見なし、一括して計算することができる.

私の答え

最初から难しかった.ううう
問題の制約要因から,入力される配列の大きさは小さい.ID user_id全体の最大長さは8なので、brute-forceメソッドを簡単に適用すれば良いだけなので、長さ順、substring、setにしましょうか?考えているうちに時間を無駄にしてしまった.
すべての状況の数を単純に確認するだけです.user_idのIDでは、banned_id個の数に応じて一致可能なIDが選択され確認される.
まずuser_idの中からbanned_idの長さrに等しいIDを選び、二次元配列vector<vector<int>> combinationsに入れる.
その後、各組合せが一致するかどうかを確認し、この過程に多くの時間を費やした.なぜなら,よく用いられる<algorithm>のnext_permutation関数が正しく理解されていないからである.
選択したIDを含むcombination[i]とbanned_idは、isMapped関数で互いに一致している.この場合、combination[i]のIDの順序によっては、一致するか、一致しないかに注意しなければならない.これもすべての順番を確認することにした.状況の数は不自然な頭脳活動より大きくないので、単純にやるともっと速くなります.combination[i]とbanned_idは同じ長さなので、combination[i][j]とbanned_id[j]は文字「*」以外で一致しているかどうか、一致しない場合はcombination[i]に並べ替えて確認してください.
この過程で同じnext_permatationnext_permatationを使用したのはもっと大きな順序で、並べ替えができれば並べ替えることができる方式なので、すべての状況の数を確認するには、並べ替えなければならない要素!!
私は本当にそれを知らない.😭 しかし私は絶対にこれを忘れないで、このような考えで、自分で撮って、ほほほ
どうせ私はこの点を知らないのに、どうしてすべての情况が确认できないのですか???私の叫びだけを叫んで、時間が経つにつれて~歩いて、やっと気づいて、直して通過しました、!

コード#コード#

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 문자열 매칭 확인 
bool isPossible(string origin, string ban){
    for (int i = 0; i < origin.length(); ++i) {
        if (ban[i] == '*') continue;
        if (origin[i] != ban[i]) return false;
    }
    return true;
}

// 매칭 가능 확인 
bool isMapped(vector<string> id, vector<string> banned){
    sort(id.begin(), id.end()); // 반드시 정렬되어 있어야!!! 모든 경우의 수 확인 가능!!!
    
    do{
        bool match = true;
        for (int i = 0; i < id.size(); ++i) {
            // 길이가 다르면 확인 필요 없음, 길이가 같으면 두 문자열 매칭 되는지 확인
            if (id[i].length() != banned[i].length() || !isPossible(id[i], banned[i])){
                match = false;
                break;
            }
        }
        if (match) return true;
    }while (next_permutation(id.begin(), id.end()));

    return false;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    int n = user_id.size(), r = banned_id.size();

    vector<bool> select(n-r, false);
    for (int i = 0; i < r; ++i)  select.push_back(true);

    // user_id에서 r개의 아이디 뽑기
    vector<vector<string>> combinations;  
    do{
        vector<string> picked;
        for (int i = 0; i < n; ++i) {
            if (select[i]) picked.push_back(user_id[i]);
        }
        combinations.push_back(picked);
    }while (next_permutation(select.begin(), select.end()));


    // 각 조합별로 모든 순열에 대해서 매칭이 한번이라도 가능하면 경우의 수 ++;
    for (int i = 0; i < combinations.size(); ++i) {
        if(isMapped(combinations[i], banned_id)) answer++;
    }

    return answer;
}