[프로그래머스]lev2 순위검색

https://school.programmers.co.kr/learn/courses/30/lessons/72412

import java.util.ArrayList;
import java.util.List;
import java.util.function.Predicate;
class Solution {
        static Predicate<String[]> valid;
       public static int[] solution(String[] info, String[] query) {
        List<Integer> answer = new ArrayList<>();

        for (int i=0; i<query.length; i++){
            setUpQuery(query[i]);
            int cnt = 0;
            for (int j=0; j<info.length; j++){
                String[] target = info[j].split(" ");
                if (valid.test(target)){
                    cnt++;
                }
            }
            answer.add(cnt);
        }
        return answer.stream()
                .mapToInt(Integer::intValue)
                .toArray();
    }
    //[1,1,1,1,2,4]
    public static void setUpQuery(final String query) {
        String[] deleteAnd = query.split(" and");
        String tmp = String.join("",deleteAnd);
        String[] target = tmp.split(" ");
        valid = (str) -> (target[0].equals("-")?true:str[0].equals(target[0])) &&
                (target[1].equals("-")?true:str[1].equals(target[1])) &&
                (target[2].equals("-")?true:str[2].equals(target[2])) &&
                (target[3].equals("-")?true:str[3].equals(target[3])) &&
                (target[4].equals("-")?true:Integer.parseInt(str[4])>=Integer.parseInt(target[4]));
    }
}

답은 맞았지만 `효율성` 부분에서 `시간초과`가 났다.

이중 for문을 사용했기 때문에 O(N2)으로 시간초과가 난듯 하다.

`이진 탐색 알고리즘`을 다시 적용했고 O(log N2) 으로 시간초과 문제를 해결할 수 있었다.

import java.util.*;

class Solution {
   static HashMap<String, ArrayList<Integer>> combs = new HashMap<>();
      static ArrayList<Integer> list;
    public static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        for (int i=0; i<info.length; i++){
            dfs(info[i].split(" "), "", 0);
        }

        ArrayList<String> keys = new ArrayList<>(combs.keySet());

        for (int i=0; i<keys.size(); i++){
            List<Integer> scores = combs.get(keys.get(i));
            Collections.sort(scores);
        }

        for (int i=0; i< query.length; i++){
            query[i] = query[i].replace(" and ","");
            String[] target = query[i].split(" ");
            int score = Integer.parseInt(target[1]);
            answer[i] = binarySearch(target[0],score);
        }
        return answer;
    }


    public static void dfs(String[] info, String sum, int idx){
        if (idx == 4){
            if (!combs.containsKey(sum)){
                list = new ArrayList<>();
                list.add(Integer.parseInt(info[4]));
                combs.put(sum,list);
            }else{
                //점수 추가
                combs.get(sum).add(Integer.parseInt(info[4]));
            }
            return;
        }
        dfs(info,sum+"-",idx+1);
        dfs(info,sum+info[idx],idx+1);
    }

    public static int binarySearch(String key, int score){
        if (!combs.containsKey(key)) return 0;

        List<Integer> scores = combs.get(key);
        int start = 0;
        int end = scores.size()-1;
        while(start<=end){
            int mid = (start+end)/2;
            if (scores.get(mid)<score){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
        return scores.size()-start;
    }

}

 

 

 

 

 

 

그림출처:

https://kangworld.tistory.com/65