2021 KAKAO BLIND RECRUITMENT - 순위 검색

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

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

---

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

public class Solution {
	
	static HashMap<String, ArrayList<Integer>> map = new HashMap();
	
	public static int[] solution(String[] info, String[] query) {
		
        int[] answer = new int[query.length];
        
        // 1. 모든 경우의수 
        for(int i=0; i<info.length; i++) {
    		// [java, backend, junior, pizza, 150]
        	String[] infoSplit = info[i].split(" ");
        	
        	comb("", 0, infoSplit);
    	}
        
//        List<Entry<String, ArrayList<Integer>>> list = new ArrayList(map.entrySet());
//        for(Entry e : list) System.out.println(e.getKey() + " : " + e.getValue());
        
        // 2. 정렬
        List<String> list = new ArrayList<>(map.keySet());
        for(String key : list) {
        	List<Integer> scoreList = map.get(key);
        	Collections.sort(scoreList);
        }
        
        
        for(int i=0; i<query.length; i++) {
        	
        	// 1. 파싱
        	// "java and backend and junior and pizza 100"
        	String queryReplace = query[i].replace(" and ", "");
        	// "javabackendjuniorpizza 100"
        	String[] querySplit = queryReplace.split(" ");
        	
        	String inf = querySplit[0];
        	int score = Integer.parseInt(querySplit[1]);
        	
        	// 3. 이진탐색
        	answer[i] = binarySearch(inf, score);
        }
        
//        System.out.println(Arrays.toString(answer));
        
        return answer;
    }
	
	public static int binarySearch(String str, int value) {
		
		if(!map.containsKey(str)) return 0;
		
		ArrayList<Integer> list = map.get(str);
		
		int start = 0;
		int end = list.size() - 1;
		
		while(start <= end) {
			int mid = (start + end) / 2;
			if(value > list.get(mid)) start = mid + 1;
			else end = mid - 1;
		}
		
		return list.size() - start;
		
	}
	
	public static void comb(String str, int depth, String[] strArr) {
		if(depth == 4) {
//			System.out.println(str);
			
			int score = Integer.parseInt(strArr[4]);
			
			if(!map.containsKey(str)) map.put(str, new ArrayList<Integer>());			
			map.get(str).add(score);
			
			return;
		}
		
		comb(str + "-", depth + 1, strArr);
		comb(str + strArr[depth], depth + 1, strArr);
	}
	
}