[プログラマー9992][2019 kakakao冬季実習]不良ユーザー問題解説

クイズクリップ

👓 問題の概要

私たちはユーザーの車を運転しなければなりません.実は私も誰が運転すべきかの原本をなくしました.可能な場合の数...彼を助けてくれませんか.まず見てから、ワゴン車を作ります・・・
文字列にアスタリスクがあります.この文字列のアスタリスクはアルファベットと数字で代用できます.条件に合ったプレイヤーを探します.
詳細については、Programmersのホームページを参照してください.問題に答える

🔑 問題を解く

アスタリスクは無条件で1文字しか対応できないので、問題は難しくありません.
2 D配列を作成した後、無効なidに対応するuser idをチェックし、それぞれの場合の数を求めると、簡単に解くことができます.

🥽 ソースコードとソースコード分析

プログラマサイトではなく、Visual Studioによって作成されたコードがインポートされます.いくつかのテストコードがあります.

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

bool isMatch[10][10]; // ban, user 순
bool isUsed[10];
int bansize = 0;
vector<vector<int>> ansVec;
bool check(string userid, string banid);
void travel(int banidx, int userNum, vector<int> ans);
int solution(vector<string> user_id, vector<string> banned_id);

int main() {

    string s = "frodo";
    string test = s.substr(4);
    vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> banned_id = { "fr*d*", "abc1**" };
    solution(user_id, banned_id);
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 1;
    bansize = banned_id.size();
    for (size_t i = 0; i < banned_id.size(); i++)
        for (size_t j = 0; j < user_id.size(); j++)
            if (check(user_id[j], banned_id[i]))
                isMatch[i][j] = true;
    int startLine = -1;

    vector<int> ans;
    travel(0, user_id.size(), ans);

    return ansVec.size();
}
void travel(int banidx, int userNum ,vector<int> ans) {
    if (banidx == bansize) {
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ansVec.size(); i++) {
            bool flag = true;
            for (int j = 0; j < ansVec[i].size(); j++){
                if (ans[j] != ansVec[i][j]) flag = false;
            }
            if (flag == true) return;
        }
        ansVec.push_back(ans);
        return;
    }
    bool isExist = false;
    for (size_t i = 0; i < userNum; i++)
        if (isMatch[banidx][i] == true) isExist = true;

    if (isExist == false) {
        travel(banidx + 1, userNum, ans);
        return;
    }

    for (size_t i = 0; i < userNum; i++){
        if (isUsed[i] == true) continue;
        if (isMatch[banidx][i] == true) {
            ans.push_back(i);
            isUsed[i] = true;
            travel(banidx + 1 , userNum, ans);
            ans.pop_back();
            isUsed[i] = false;
        }
    }
}
bool check(string user, string ban) {
    if (user.size() != ban.size()) return false;
    for (size_t i = 0; i < ban.size();i++)
    {
        if (user[i] != ban[i] && ban[i] != '*') return false;
    }
    return true;
}

🔨 問題ポスト

BANNEDを*で扱うプレイヤーのSense...
よく考えているが、問題は現実の要求を反映していないようだ.