[Lv_2] 순위검색

🔍 아이디어

✅ 지원자들의 스펙을 가능한 모든 경우의 수를 구해 _!Map!_ 의 _!key!_ 로 저장한다.

✅ 저장한 곳의 _!value!_ 에는 지원자의 점수를 저장해두고, 모든 순회가 종료되면 오름차순으로 정렬한다.

✅ _!query!_ 를 저장해둔 _!key!_ 의 형태로 변환하고 저장된 값이 있는지 찾는다.

✅ 값이 있다면, _!query!_ 의 코딩 기준 점수보다 높은 사람이 몇 명이 있는지 구하고, _!answer!_ 변수에 담아 반환한다.

import java.util.*;

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        for (String info_str : info) {
        	// 지원자의 스펙, 변화 가능 경우의 수 구하기
            dfs(0, info_str.split(" "), new boolean[4]);
        }
        
        for (String key : map.keySet()) {
        	// 각 스펙별 점수 오름차순 정렬
            Collections.sort(map.get(key));
        }
        
        int i = 0;
        for (String str : query) {
            String[] split = str.split(" ");
            int validNum = Integer.parseInt(split[split.length - 1]);
            String key = str.replaceAll("and| |[0-9]", "");
            List<Integer> val = map.getOrDefault(key, null);
            if (val != null) {
            	// query로 만든 key로 값을 찾을 수 있다면, 값 내에서 몇 번째인지 찾는다.
                answer[i] = findManyPerson(val, validNum);
            } else {
                answer[i] = 0;
            }
            
            i++;
        }
        
        return answer;
    }
    
    int findManyPerson(List<Integer> val, int validNum) {
        int left = 0;
        int right = val.size();
                
        while (left < right) {
            int mid = (left + right) / 2;
            if (val.get(mid) >= validNum) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return val.size() - left;
    }
        
    void dfs(int depth, String[] arr, boolean[] check) {
        if (depth == 4) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < check.length; i++) {
                boolean bool = check[i];
                if (bool) {
                    sb.append(arr[i]);
                } else {
                    sb.append("-");
                }
            }
            
            String key = sb.toString();
            
            if (map.containsKey(key)) {
                map.get(key).add(Integer.valueOf(arr[4]));
            } else {
                map.put(key, new ArrayList<>(List.of(Integer.valueOf(arr[4])))); 
            }
                
            return;
        }
        
        dfs(depth + 1, arr, check.clone());
        check[depth] = true;
        dfs(depth + 1, arr, check.clone());
    }
}

✔️ 링크 : 코딩테스트 연습 - 순위 검색 | 프로그래머스 스쿨 (programmers.co.kr)