プログラマ-ランキング検索

1.質問

質問リンク
説明:
コカソは下半期にベテラン開発者を公開募集しており、応募とコードテストは終了している.今回の募集では、応募者は申請書に記入する際に以下の4つを選択しなければなりません.

が符号化テストに参加する開発言語プロジェクトでcpp、java、pythonを選択する必要があります.

の「サポート担当者」エントリでバックエンドとフロントエンドを選択する必要があります.

応募履歴区分項目では、低学年と高学年から選択します.

は第一選択の魂の食品で、鶏肉とピザの中から1つを選択する必要があります.

人材導入チームで働くNiniesは、コードテストの結果を分析し、採用に参加する開発チームにサポート条件を提供することで、これらの条件に合致する応募者が何人いるかを簡単に理解できるツールを作成しています.
たとえば、開発チームが知りたい問題は次のとおりです.
Javaでコードテストに参加し、バックグラウンドの職業を選び、初級経験を持ち、SoulFoodピザを選んだ人のうち、50点以上のコードテスト点数を獲得した人は何人いますか?
もちろん、各開発チームの状況によっては、次のような問題が発生する可能性があります.

符号化テストで、frontend直軍、ベテラン、soulfood rochickenを選んで100点以上の符号化テスト点数を獲得した人は何人いますか?

cppとして

のコードテストに参加しましたが、ベテランの中でsoulfoodピザを選んだ人のうち、コードテスト点数100点以上の人は何人いますか?

バックグラウンドの直軍を選んで、高級な経験があって、コードのテストの点数の200点以上の合計は何人ですか?

でsoulfood rochickenを選択した人のうち、250点以上の符号化テスト点数を獲得した人は何人いますか?

コードテストで150点以上を取った人は何人いますか?

これは、開発チームが次のことを理解したいことを意味します.

[条件]を満たす人のうち、コードテストX点以上を取得した人は何人いますか?

質問する
サポート担当者がサポート書に入力した4つの情報と、得られた符号化テスト点数を1つの文字列に構成する場合、配列情報および開発チームが好奇心を持っているクエリー条件が文字列形式で提供される配列クエリーをパラメータとする場合.
解答関数を完了し、各ドアの条件に合致する人数を順番に並べて返してください.
せいげんじょうけん

info配列のサイズは50000を超えない.

info配列の各要素の値は「開発言語職業経歴魂食品点数」の形式であり、ボランティアが申請書に入力した4つの値をコードテスト点数に加算する.

開発言語はcpp、java、pythonです.

直軍は後端と先端の一つである.

の経歴は大三中の一つである.

ソウルフードは鶏肉、ピザの一つです.

点とは、1または100000未満の符号化試験点数の自然数を指す.

各単語はスペースで区切られています.

query配列のサイズは100000を超えません.

queryの各文字列は、「[条件]X」形式です.

[条件]は、「言語と職業、経歴、魂の食品を開発する」形式の文字列です.

言語はcpp、java、python、および-の1つです.

直軍は後端、先端、-の一つである.

の経歴は中学校、高校-その一つです.

ソウルフードはチキンピザです

"-"は、これらの条件を考慮しないことを示す.

Xはコードテスト点数を表し、条件を満たす人の中で、X点以上の人は全部で何人いますか.

各単語はスペースで区切られています.

を例にとると、「cpp and-andhigher and pizza 500」は「cppでコードテストを行った経験がベテランで、soulfoodをpizzaとして選んだ応募者のうち、コードテスト点数500点以上の人は何人いますか?」に表示されます.

2.解答

この問題はinfoアレイのみで、完全なナビゲーションを行うとタイムアウトします.
ブラウズに適した最適なテーブルを作成し、Xポイント以上の数を検索することができます.
「low boundを使うのがちょうどいい」
計画1-ナビゲーション可能な最適なテーブルの作成

const map = info.reduce((m, v) => {
    v = v.split(' ');
    const score = Number(v[4]);

    (function f(depth, key) {
        if (depth == 4) {
            m[key] = m[key] || [];
            m[key].push(score);
            return;
        }

        f(depth + 1, key + '-'); // 포함시키지 않거나
        f(depth + 1, key + v[depth]); // 포함시키거나
    })(0, '');

    return m;
}, {});

infoの周りに配置され、各参加者に対する情報
すべての場合、結合キー(含むか含まないか)を作成します.
対応するスコアを配列にプッシュします.
計画2-計画1で作成したテーブルのすべての配列を整列

Object.values(map).forEach((scores) => scores.sort((a, b) => a - b));

lower_boundを使用するには、まずソートする必要があります.
計画3-lower_boundを使用してクエリーを実行

return query.map((q) => {
    const key = q.replace(/ and |\s\d+$/g, ''); // 정규식으로 키 추출
    const scores = map[key]; // 키에 해당하는 array

    if (!scores) return 0; // array가 undefined, 즉 존재 안함

    const score = Number(q.match(/\d+$/)[0]); // 정규식으로 점수 추출
    let s = 0;
    let e = scores.length;

    while (e > s) { // lower_bound 수행
        const mid = Math.floor((s + e) / 2);

        if (scores[mid] < score) {
            s = mid + 1;
        }
        else {
            e = mid;
        }
    }

    return scores.length - e;
});

このようにして行うと,タイムアウトせずに問題を通過することができる.

3.完全なコード

function solution(info, query) {
    const map = info.reduce((m, v) => {
        v = v.split(' ');
        const score = Number(v[4]);

        (function f(depth, key) {
            if (depth == 4) {
                m[key] = m[key] || [];
                m[key].push(score);
                return;
            }

            f(depth + 1, key + '-');
            f(depth + 1, key + v[depth]);
        })(0, '');

        return m;
    }, {});

    Object.values(map).forEach((scores) => scores.sort((a, b) => a - b));

    return query.map((q) => {
        const key = q.replace(/ and |\s\d+$/g, '');
        const scores = map[key];

        if (!scores) return 0;

        const score = Number(q.match(/\d+$/)[0]);
        let s = 0;
        let e = scores.length;

        while (e > s) {
            const mid = Math.floor((s + e) / 2);

            if (scores[mid] < score) {
                s = mid + 1;
            }
            else {
                e = mid;
            }
        }

        return scores.length - e;
    });
}