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

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

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

[문제]

[풀이]

info가 주어지고 query가 주어졌을때 , 조건에 맞는 지원자의 수를 return 하는 문제이다.
우선 , info 와 query가 최악일 경우 5억번이 주어지므로 시간복잡도는 낮추기 위해서
info 자체를 map으로 따로 뺀 다음 , 조건에 맞는 수 만큼 카운팅하는 접근으로 해야된다.

<key , score[]> 형태로 javabackendjuniorpizza 이 key가 되고 150이 score가 되어
map에 저장해야 된다는 뜻.

저장이 다 끝났으면 query배열을 순회하는데 , 여기서 그냥 순회하니깐 효율성 0점이 나와서
다른사람의 코드를 보니 이진탐색을 통해서 시간을 더 줄여야 한다고 하더라 ..

그래서 저 score[]를 한번 정렬 한 다음에 이진탐색으로 하니 통과

 
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        String[] info={"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"};
        String[] query={"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"};
        sol.solution(info,query);
    }
}
 
class Solution {
    HashMap<String,ArrayList<Integer>> infoMap = new HashMap<>();
    ArrayList<Integer> ans = new ArrayList<>();
    public int[] solution(String[] info, String[] query) {
 
        for (String s : info) combination("", 0, s.split(" "));
        infoMap.values().forEach(Collections::sort);
 
        for (String q : query) {
            String[] split = q.replaceAll(" and ", "").split(" ");
            String key = split[0];
            int score = Integer.parseInt(split[1]);
            ans.add(counting(key, score));
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
 
    int counting(String str,int score){
        if(!infoMap.containsKey(str)) return 0;
 
        List<Integer> list=infoMap.get(str);
        int start=0,end=list.size()-1;
 
        while(start<=end){
            int mid=(start+end)/2;
            if(list.get(mid)<score) start=mid+1;
            else end=mid-1;
        }
        return list.size()-start;
    }
 
    public void combination(String key,int depth,String[] info){
        if(depth==4){
            int score = Integer.parseInt(info[4]);
            if(!infoMap.containsKey(key)){
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                infoMap.put(key,list);
            }else infoMap.get(key).add(score);
            return;
        }
        combination(key+"-",depth+1,info);
        combination(key+info[depth],depth+1,info);
    }
 
}