[アルゴリズム回答]検索プログラマーランキング

Kakao機出泡機!今回解決した問題はkakao 2021ブラインド求人-ランキング検索!先日解けましたが、最近プロジェクトが忙しくて、今宣伝しました...
問題の説明
[この問題は精度と効率テストで1点ずつ占めています]
コカソは下半期にベテラン開発者を公開募集しており、応募とコードテストは終了している.今回の募集では、応募者は申請書に記入する際に以下の4つを選択しなければなりません.

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

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

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

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

人材導入チームで働くNiniesは、コードテストの結果を分析し、採用に参加する開発チームにサポート条件を提供することで、これらの条件に合致する応募者が何人いるかを簡単に理解できるツールを作成しています.
たとえば、開発チームが知りたい問題は次のとおりです.

코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 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点以上の人は何人いますか?」に表示されます.

I/O例
infoqueryresult["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"][1,1,1,1,2,4]
解答方法
効率的な問題はいつも難しい.効率が通らなければ、アクセス自体が間違える可能性があるので、再開する時間が足りず、初めてアクセスする方法が頭に残っているので、新しい方法が思いつかない.
まず、効率を上げるためには、情報の前処理が必要だと思います.1つ目の方法はinfoを4 c文字に変換することです.cpp:1 java:2はこのようにマッピングされます.また、query検索を行う場合も同様の変換を行いますが、考慮しない-文字は.正規検索を使用して検索できるように変換します.しかし効率的にも通らなかった.
制限事項から見ると、現在のようにqueryごとに各情報が検索されているのは、検索効率をどのように向上させても各サイズが50000000であり、両者を乗じると時間の複雑さが現れるため、誤ったアクセスである可能性があるからである.では、前処理後は、情報を閲覧する必要がないように前処理を行います.そこで,現在の条件では,各情報に含まれる可能性のあるすべてのケースの数を求めた.すなわちjava後端子pizzaには4つの条件があり,それぞれ所定値毎と考慮しない場合があり,そのうち2^4=16の場合がある.このように、16個に変換された4 c文字をキーとして、対応する符号化試験点数を含むリストvalueのmapを用いて前処理を行う.すなわち、infoが満たすことができるすべてのqueryの場合、対応する符号化テスト点数が加算される.
その後、queryの対応する4 c文字をキーとして使用して、要求を満たすボランティアの符号化テスト点数に直接アクセスすることができる.上記の情報はすべて閲覧する必要はありません!エンコードテストスコアリストに満足するスコアを見つけます.最初から最後までの探索を避けるために,まずリストをソートする.これで、queryで所定の条件以上の値の最小要素が見つかった場合、インデックスを使用して整数を直接求めることができます.そこで,二分ルックアップを用いて値のインデックスを求め,それを用いて直接整数を求め,戻り結果配列に入れる.
この問題は,入力文字列の処理,処理前の処理中に遡及的な組合せを用いて資料構造に効率的に格納し,次いで二分検索により名数を迅速に求めるなど多くのアルゴリズムに関し,かなり厄介な問題である.果たしてなぜレベル2なのか???
コード#コード#

import java.util.*;

class Solution {
    public static Map<String, String> languageMapper = new HashMap<>(){{
        put("cpp", "1");
        put("java", "2");
        put("python", "3");
    }};
    public static Map<String, String> jobMapper = new HashMap<>(){{
        put("backend", "1");
        put("frontend", "2");
    }};
    public static Map<String, String> careerMapper = new HashMap<>(){{
        put("junior", "1");
        put("senior", "2");
    }};
    public static Map<String, String> foodMapper = new HashMap<>(){{
        put("chicken", "1");
        put("pizza", "2");
    }};

    public static ArrayList<Map<String, Integer>> maps = new ArrayList(Arrays.asList(languageMapper, jobMapper, careerMapper, foodMapper));

    public static Map<String, ArrayList<Integer>> infoSet;
    public static boolean[] visited;

    public static String convert(String[] info){
        String result = "";
        for(int i=0; i<4; i++){
            if(!maps.get(i).containsKey(info[i])) result += "-";
            else result += maps.get(i).get(info[i]);
        }
        return result;
    }

    public static void combination(String info, char[] result, boolean[] visited, int r, int cur, int score){
        if(r == 0){
            String temp = new String(result);
            if(!infoSet.containsKey(temp)) infoSet.put(temp, new ArrayList<>());
            infoSet.get(temp).add(score);
            return;
        }
        for(int i=cur; i<info.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                result[i] = info.charAt(i);
                combination(info, result, visited, r-1, i+1, score);
                result[i] = '-';
                visited[i] = false;
            }
        }
    }

    public static void addCased(String info, int score){
        for(int i=0; i<=4; i++){
            visited = new boolean[info.length()];
            combination(info, "----".toCharArray(), visited, i, 0, score);
        }
    }
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        infoSet = new HashMap<>();
        String[] eachInfo;
        for(String str : info){
            eachInfo = str.split(" ");
            addCased(convert(eachInfo), Integer.parseInt(eachInfo[4]));
        }
        Set<String> keys = infoSet.keySet();
        for(String key : keys){
            infoSet.get(key).sort(Comparator.naturalOrder());
        }
        int left, right, mid, score;
        ArrayList<Integer> target;
        String key, str;
        for(int i=0; i<query.length; i++){
            str = query[i];
            str = str.replace("and ", "");
            eachInfo = str.split(" ");
            key = convert(eachInfo);
            score = Integer.parseInt(eachInfo[4]);
            if(!infoSet.containsKey(key)) continue;
            target = infoSet.get(key);
            left = 0;
            right = target.size()-1;
            while(left < right){
                mid = (left + right) / 2;
                if(target.get(mid) < score) left = mid+1;
                else right = mid;
            }
            answer[i] = target.size() - left;
        }
        return answer;
    }
}