問題の説明

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

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

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

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

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

人材導入チームで働くNiniesは、コードテストの結果を分析し、採用に参加する開発チームにサポート条件を提供することで、これらの条件に合致する応募者が何人いるかを簡単に理解できるツールを作成しています.
たとえば、開発チームが知りたい問題は次のとおりです.코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

質問する

サポート担当者がサポート書に入力した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]
例えば、「言語、職業、経歴、ソウルフード、点数」の順に、以下のようになります.
言語職業経歴soulfood点数javackendjuniorpizza 150 pythonfrontende年長鶏210 pythonfrontende年長鶏150 cpbackndjuniorpizza 260 javackendjuniorchiken 80 pythonbackend年長鶏50
「java and backend and junior and pizza 100」と聞かれたらjavaでコードテストを行い、バックグラウンド直軍、初級経歴、SoulFoodピザを選んだ応募者のうち、100点以上のコードテスト点数を取った応募者は1人です.このような結果が得られる.- and - and - and - 150のqueryであれば、150点以上のコードテスト点数を獲得した応募者は4人いる.このような結果を出せばよい.

に答える

最初は、すべての情報をリストに入れて、一つ一つ回るつもりでしたが、事実はそうではありません.
効率テストを含む問題なので、時間的によく計算して解答します.
の順にクリックします.
1.すべての情報を1つのセットに配置して検索します.
2.同様に、queryもCollectionに配置され、最初のCollectionで検索され、条件に合致するユーザが計算される.△ここまでは同じです.
第1の例では、可能なすべての情報조합がMapに格納される.
2番目の検索では이진탐색によって検索された.

// 조합 코드

Map<String, List<Integer>> allCases = new HashMap<>();


for(int i = 0; i < info.length; i++) {
	String[] infos = info[i].split(" ");
	makeAllCases("", 0, infos); // 만들 문자열(조합된 결과), 현재 인덱스, 해당 info 배열 
}


public void makeAllCases(String str, int idx, String[] infos) {
	
    if(idx == 4) {
    	if(!allCases.containsKey(str)) {
        	List<Integer> scores = new ArrayList<>();
            allCases.put(str, scores);
        }
        
        allCases.get(str).add(Integer.parseInt(infos[4]));
        return;
    }
    
    
    // 조건과 관계 없을 때
    makeAllCases("" + "-", idx + 1, infos);
    
    // 조건이 있을 때
    makeAllCases("" + infos[idx], idx + 1, infos);
}

次に、マッピング内のすべてのcaseでqueryに対応する状況を検索する必要があります.バイナリ検索で検索するため、スコアをソートする必要があります.

// 정렬
for(String s : allCases.keySet()) {
	Collections.sort(allCases.get(s));
}


// 이진탐색
for(int i = 0; i < query.length; i++) {
	String removedAndQuery = query.replace(" and ", "");
    
    String[] keyAndValue = removedAndQuery.split(" ");
    int res = allCases.containsKey(keyAndValue[0]) ? binarySearch(keyAndValue[0], Integer.parseInt(keyAndValue[1]) : 0;
}


public int binarySearch(String key, String value) {
	List<Integer> scores = allCases.get(key);
    
    int low = 0;
    int high = scores.size() - 1;
    
    while(low <= high) {
    	int mid = (low + high) / 2;
        
        if(socres.get(mid) < value) low = mid + 1;
        else high = mid - 1;
    }
    
    return socres.size() - low;   
}

完全なコード

class Solution {

    Map<String, List<Integer>> allCases = new HashMap<>();

    public int[] solution(String[] info, String[] query) {
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < info.length; i++) {
            makeAllCases("", 0, info[i].split(" ")); // 현재까지 만들어진 문자열, 현재 인덱스, info 배열
        }

        for (String s : allCases.keySet()) {
            Collections.sort(allCases.get(s));
        }


        for(int i = 0; i < query.length; i++) {
            String removedAndQuery = query[i].replace(" and ", "");
            String[] keyAndValue = removedAndQuery.split(" ");
            int caseRes = allCases.containsKey(keyAndValue[0]) ? binarySearch(keyAndValue[0], Integer.parseInt(keyAndValue[1])) : 0;
            res.add(caseRes);
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }


    // 해당 info가 가질 수 있는 모든 조합 : key, 그 조건을 가진 점수 : value 로 map을 구성한다.
    public void makeAllCases(String curStr, int cnt, String[] infos) {

        if (cnt == 4) {
            if (!allCases.containsKey(curStr)){
                List<Integer> list = new ArrayList<>();
                allCases.put(curStr, list);
            }
            allCases.get(curStr).add(Integer.parseInt(infos[4]));
            return;
        }

        makeAllCases(curStr + infos[cnt], cnt + 1, infos);
        makeAllCases(curStr + "-", cnt + 1, infos);
    }

    // 이진탐색
    public int binarySearch(String key, int value) {
        List<Integer> scores = allCases.get(key);

        int low = 0;
        int high = scores.size() -1;

        while (low <= high){
            int mid = (low + high) / 2;

            if (scores.get(mid) < value) low = mid + 1;
            else high = mid - 1;
        }

        return scores.size() - low;
    }
}