프로그래머스 - [Level 2] 순위 검색(JAVA)

프로그래머스 순위 검색[2021 카카오 블라인드]

카테고리 : 이분탐색/Upper Bound

'-' 와 최대 100,000 점이 되는 점수를 어떻게 처리하는지가 핵심이다.
풀이과정은 다음과 같다.

1) info[] 배열로 '-'를 포함한 모든 경우의 수를 만들어준다.

1) - 1
경우의 수를 String 으로 만들어준다.
예를들어, java backend junior pizza 150이 주어진경우
나올 수 있는 경우의 수는 다음과 같다.

1) - 2 
모든 경우의 수를 Map<String,List<Integer>> map에 {string,list} 쌍으로 저장한다.
모든 경우의 수에 해당하는 점수를 list에 보관하기 위해서이다.
이때, Map의 key 값에는 '1) - 1' 에서 만들어준 string 값이 들어간다는 점을 참고하자.

query[] 배열을 돌며 query에 해당하는 map 값을 조회하면 아래와 같다.

2) 이분 탐색을 통해 답을 구해준다.

이제, 이분탐색을하며, 답을 카운팅해줘야한다.
순차적으로 탐색하면 "시간초과"가 발생한다.

이분탐색으로 
"목표 점수>list[idx] && 목표점수 <=list[idx]"
에 해당하는 'index'를 구해준다.

"x 점 이상 받은 사람은 모두 몇 명인가?"를 구해야하고,
한 list 안에 동일한 점수가 존재할 수 있기 때문에
조건을 만족하는 가장 작은 index 값을 선택해야한다.

이후, index가 구해졌다면 list.size()-index 를 해주면 답이된다.

소스 코드

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.List;
import java.util.Collections;
import java.util.Iterator;

class Solution {
    static ArrayList<ArrayList<Integer>> list=new ArrayList<>();    
    static Map<String,List<Integer>> map=new HashMap<>();
    static int[] answer;
    
    static void dfs(String str,int depth,String[] info){
        if(depth==4){
            if(map.containsKey(str)==false){
                List<Integer> list=new ArrayList<>();
                list.add(Integer.parseInt(info[4]));
                map.put(str,list);
            }else{
                map.get(str).add(Integer.parseInt(info[4]));
            }
            return;
        }
        
        dfs(str+"-",depth+1,info);
        dfs(str+info[depth],depth+1,info);
    }
    
    static void setInfo(String[] info){
        for(int i=0;i<info.length;i++){
            dfs("",0,info[i].split(" "));
        }
        
        Iterator<String> it= map.keySet().iterator();
        while(it.hasNext()){
            String key=it.next();
            List<Integer> li=map.get(key);
            Collections.sort(li);
        }
    }
    
    static int counting(String str,int score){
        if(map.containsKey(str)==false) return 0;
        
        List<Integer> list=map.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;
    }
    
    static void makeAnswer(String[] query){
        for(int i=0;i<query.length;i++){
            String str="";
            String[] arr=query[i].split(" ");
            
            for(int j=0;j<arr.length-1;j++){
                if(arr[j].equals("and")) continue; 
                str+=arr[j];
            }
            answer[i]=counting(str,Integer.parseInt(arr[arr.length-1]));
        }
    }
    
    public int[] solution(String[] info, String[] query) {
        answer = new int[query.length];
        setInfo(info);
        makeAnswer(query);
        return answer;
    }
}