プログラム・デザイナのランキング検索

マジシャンです

比喩問題では、「ある表でSELECTを求めるときの結果数」とあまり差がありません.
ただし,WHERE節には複数の条件があり,与えられたデータは表形式ではなくStringである.効率テストもあります.

方法

初期の方法は、各行がボランティア情報を検索し、2階建ての砲口にいくつかのif条件を加えることだった.精度テストに合格しましたが、効率テストがタイムアウトしました.
別の方法を考え出そうと…!!

1.HashMapに対応するクエリーを検索させる

HashMapでは、そのqueryと同じ内容があれば数字を計算し、なければ0と呼ぶ.
では、HashMapをinfo配列で埋め込むには、どうすればいいのでしょうか.
サンプルデータを取得します
「java backend junior pizza 150」では、前の4つの単語と後の数字を分けて見ると、「javabendjunior pizza」をキーとして150を値とすれば、完全にHashMapに入れることができます.
ただし、キーが同じでvalueが異なる重複が発生する可能性があります.これに対応するためにvalue形式をListとする.
ただし、上記の例のデータ「javabackendjunior pizza」は「-backed-pizza」として参照することもできます.また、「java---」と参照することもできます.つまり、javabackendjuniorpizaを参照するには、「-」が含まれているすべての場合、HashMapに入れる必要があります.
「-」のすべての状況をどのように取得しますか?-->部分集合を利用すればいい!
今では上の方法でHashMapを充填しています.

2.リストで質問点数以上の数字を求める

「---」のようなキーはvalueのリストのサイズが大きいに違いない.そのリストでは、あなたの点数があなたの質問点数より大きい場合は、数を求めます.良い方法はないですか?
リストを並べ替えた後,二分探索により,クエリスコア以上の値が最初に現れる点のインデックスを取得し,リストの大きさからインデックス値を減算することで,クエリ条件に合致する応募者の数を得ることができる.
(1,2,3,4,4,6,7,8)リストがある場合、1つ数えて4以上あれば、4以上で初めて出てくるインデックスは3です.Listの大きさは9なので、9-3と言えば6です.
求めた値を順番に答えに入れればいいです.

コード#コード#

import java.util.*;
class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        HashMap<String, List<Integer> > hm = new HashMap<>();//해시맵
        boolean[] chk = new boolean[4];//부분집합에 쓰이는 boolean 배열
        
        //recur를 통해 부분집합의 경우의 수 만큼 해시맵에 넣어준다.
        for(int i = 0 ; i < info.length; i++){
            String[] infos = info[i].split(" ");
            recur(hm, infos, 0, chk);
        }
        
        //value의 List들을 다 정렬 해준다.
        for(String qr : hm.keySet()){
            Collections.sort(hm.get(qr));
        }
        
        //해당 문의가 해시맵에 있는지 확인하고 
        for(int i = 0; i < query.length; i++){
            String[] x = query[i].split(" ");
            StringBuilder sb = new StringBuilder();
            sb.append(x[0]).append(x[2]).append(x[4]).append(x[6]);
            String qr = sb.toString();
            int num = Integer.parseInt(x[7]);
            if(!hm.containsKey(qr)) continue;
            else{
            //해당 문의가 해시맵에 있다면, 문의 점수이상의 점수가 처음으로 나오는 지점을 이분탐색을 통해 구한다.
                List<Integer> ml = hm.get(qr);
                answer[i] = myBSearch(ml, num);
            }
        }
        return answer;
    }
    
    //이분 탐색 메소드
    private static int myBSearch(List<Integer> ml, int num){
        int start = 0;
        int end = ml.size();
        while(start < end){
            int mid = (start + end) / 2;
            if(ml.get(mid) < num)
                start = mid + 1;
            else
                end = mid;
        }
        //이분 탐색후 List의 크기 - 해당 점수가 처음으로 나온 인덱스의 값은 
        //해당 점수보다 이상인 점수들의 개수이므로 이 값을 바로 리턴하게 해줌
        return ml.size() - end;
    }
    //부분 집합 메소드
    private static void recur(HashMap<String, List<Integer> > hm, String[] x, int cnt, boolean[] chk){
        if(cnt == 4){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < 4 ; i++){
                if(chk[i]) sb.append(x[i]);
                else sb.append("-");
            }
            String res = sb.toString();
            //이미 해시맵에 있다면 List에 add해준다.
            if(hm.containsKey(res)){
                hm.get(res).add(Integer.parseInt(x[4]));
            }else{
            //없다면 새로 List를 만들어 해시맵에 넣어준다.
                List<Integer> ml = new ArrayList<>();
                ml.add(Integer.parseInt(x[4]));
                hm.put(res, ml);
            }
            return;
        }
        chk[cnt] = true;
        recur(hm, x,cnt+1 ,chk);
        chk[cnt] = false;
        recur(hm, x,cnt+1 ,chk);
    }
}