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

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

코딩테스트 연습 - 순위 검색

 

무지성 무효율 풀이

public static int[] Solution(String[] info, String[] query){
        ArrayList<Integer> arr = new ArrayList<>();
        int flag = 0;int cnt =0;
        for(int i=0;i<query.length;i++){
            cnt=0;
            String[] qArr = query[i].split(" and | ");
            for(int j=0;j<info.length;j++){
                flag=0;
                String[] infArr = info[j].split(" ");
                for(int k=0;k< qArr.length - 1;k++){
                    if(qArr[k].equals("-") || qArr[k].equals(infArr[k])) continue;
                    else {
                        flag=1; break;
                    }
                }
                if(flag==0) {
                    if(Integer.parseInt(qArr[4]) <= Integer.parseInt(infArr[4]))
                    cnt++;
                }
            }
            arr.add(cnt);
        }
        int[] answer = arr.stream().mapToInt(i -> i).toArray();
        return answer;
    }

 

hashmap, bitmasking, binarysearch를 깃들인 정답풀이

import java.util.*;
class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> map = new HashMap<>();
        for(String in : info){
            String[] split = in.split(" ");
            for(int i=0;i<(1<<4);i++){
                StringBuilder key = new StringBuilder();
                for(int j=0;j<4;j++){
                    if((i&(1<<j))>0){
                        key.append(split[j]);
                    }
                }
                map.computeIfAbsent(key.toString(), s -> new ArrayList<Integer>()).add(Integer.parseInt(split[4]));
            }
        }
        for(Map.Entry<String, List<Integer>> entry : map.entrySet()) entry.getValue().sort(null);
        int[] answer = new int[query.length];
        for(int i=0;i< query.length;i++){
            String[] splits = query[i].replaceAll("-","").replaceAll(" and ","").split(" ");
            List<Integer> list = map.getOrDefault(splits[0],new ArrayList<Integer>());
            int start = 0; int end = list.size();
            int value = Integer.parseInt(splits[1]);
            while(start<end){
                int mid = (start+end)/2;
                if(list.get(mid)<value){
                    start = mid+1;
                }else{
                    end = mid;
                }
            }
            answer[i]=list.size()-start;
        }
 
        return answer;
    }
}