質問する

質問リンク

これは、データの後にクエリーを処理する問題です.
簡単に文字列に切って、数えておけばいいと思っていました.

インプリメンテーション

挑戦する方法は、列数で並べてカウントダウンを行うことです.

// 간단한 처리를 위해 문자를 각각 012로 매칭함.
int[][][][][] data;

データを記入すると問題になります.
例:
100点以上のすべてのデータを得るためには,簡単に考えれば順次巡回が可能である.
しかし、一見非効率的だ.
各インデックスにデータの数があるとします.次のようにします.
0 1 2 3 4 5 6 7 8 9 ...
0 0 1 0 0 2 0 0 0 0 ...
では、2より大きいデータを探すためには[2,data.length()]を求める必要があり、真ん中に0のデータが挟まっていると困る.
(セグメントツリーをしばらく使うべきだと思いますが、すべての組み合わせのツリーを作成するのはメモリがかかりすぎて、実装も難しいかもしれません.)
だから配列に追加する方法でデータを入れるべきだと知っています.
では[2,5,5,10,15,20]とともにデータが存在する場合,5の最小インデックスを求めれば5以上のデータ数が分かる.
これはバイナリ検索によって実現できる.
(javaでは、複数の配列を使用してソートする場合は、各次元を比較する必要があります.
したがって、複数の配列を使用するのではなく、Stringに変換してMapに変換します.)

時間の複雑さ

ピザ100というデータがあれば
最初から-セルのすべての状況を考慮した数を先に含めるかどうか.
または、後でクエリーを処理するときに複数の計算を選択できます.

複数計算クエリー

まず、入力データをmapに処理するには、入力データの個数に等しい時間が必要である.(5万)
クエリーは、cpp、java、pythonのようにすべての複数の選択を処理する必要があるため、各基数を乗算する必要があります.
では、3 x 2 x 2 x 2 x 2 xクエリ数(10万)の大きなクエリを処理する必要があります.
=>24 x 10万=240万
各クエリーはバイナリツリーで処理されます.
リスト長をn(最大5万)と呼ぶとlogn(最大16)と同じ時間がかかります.
すなわち、5 x 10^4 x 240 x 10^4 x 16=19200 x 10^8(19200秒)
△このように解いても、効率テストに合格した.

可能なすべての入力を挿入

ただし、入力データを初めて処理するときに重複データまで入れると
5万x 24の時間がかかりますが
クエリーは一度だけ処理できます.10万x 16
最終的な時間複雑度は5 x 10^4 x 10 x 10^4 x 16=800 x 10^8(800秒)である.

コード#コード#

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> map=new HashMap<>();
        setMap(map,info);
        sortMap(map);
        int[] ans = solve(query,map);
        return ans;
    }
    void setMap(Map<String, List<Integer>> map,String[] info){
        for(String inf:info){
            StringTokenizer stk=new StringTokenizer(inf);
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<4;i++) sb.append(stk.nextToken());
            int score=Integer.parseInt(stk.nextToken());
            // push to map
            if(!map.containsKey(sb.toString())){
                List<Integer> arr=new ArrayList<>();
                arr.add(score);
                map.put(sb.toString(),arr);
            }
            else{
                List<Integer> arr = map.get(sb.toString());
                arr.add(score);
            }
        }
    }
    void sortMap(Map<String, List<Integer>> map){
        for(List<Integer> arr:map.values()){
            Collections.sort(arr);
        }
    }
    int[] solve(String[] query, Map<String, List<Integer>> map){
        List<String> listA=new ArrayList<>();
        List<String> listB=new ArrayList<>();
        List<String> listC=new ArrayList<>();
        List<String> listD=new ArrayList<>();
        int[] ret=new int[query.length];
        int score;
        int idx=0;
        for(String str:query){
            String[] strList=str.split(" and | ");

            listA.clear();
            String queryA=strList[0];
            if(queryA.equals("-")) {listA.add("cpp");listA.add("java");listA.add("python");}
            else listA.add(queryA);

            listB.clear();
            String queryB=strList[1];
            if(queryB.equals("-")) {listB.add("backend");listB.add("frontend");}
            else listB.add(queryB);

            listC.clear();
            String queryC=strList[2];
            if(queryC.equals("-")) {listC.add("junior");listC.add("senior");}
            else listC.add(queryC);

            listD.clear();
            String queryD=strList[3];
            if(queryD.equals("-")) {listD.add("chicken");listD.add("pizza");}
            else listD.add(queryD);

            score=Integer.parseInt(strList[4]);

            int tmp=0;
            for(String strA:listA){
                for(String strB:listB){
                    for(String strC:listC){
                        for(String strD:listD){
                            StringBuilder sb=new StringBuilder();
                            sb.append(strA);sb.append(strB);
                            sb.append(strC);sb.append(strD);
                            // 이진탐색으로 tmp 에 더함
                            tmp+=getLowerBound(sb.toString(),score,map);
                        }
                    }
                }
            }
            ret[idx++]=tmp;
        }
        return ret;
    }
    int getLowerBound(String query,int score,Map<String, List<Integer>> map){
        // map 에서 score list 받기
        List<Integer> scoreList;
        if(!map.containsKey(query)) return 0;
        scoreList=map.get(query);

        // scoreList 가 있다면 로어 바운드로 score 이상값중 낮은 인덱스 찾기
        int s=0,e=scoreList.size()-1;
        int lbound=-1;
        int ret=0;
        while(s<=e){
            int mid=(s+e)/2;
            if(scoreList.get(mid)>=score) {e=mid-1;lbound=mid;}
            else s=mid+1;
        }
        if(lbound==-1) return 0;
        else return (scoreList.size()-lbound);
    }
}