[2021 KAKAO BLIND RECRUITMENT] 순위 검색

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72412

이 문제는 HashMap과 이진 탐색을 이용하여 풀 수 있습니다. 문제에서 주어진 info값을 하나의 문자열로 만들어 키로 Map에 추가합니다. 이 때 value값은 점수가 됩니다. 같은 조건일 때 여러 점수가 나올 수 있으므로 점수는 List로 추가합니다. 또한 문제 조건에서 -의 경우 모든 조건이므로 이 부분을 재귀함수를 이용하여 같이 추가해줍니다.

조건을 만족시키는 수를 더 빠르게 탐색하기 위해 이진 탐색을 진행합니다. 이를 위해 List를 오름차순으로 정렬을 먼저 진행합니다. min을 0, max를 List의 최대 인덱스로 설정한 후 mid를 계산하여 mid가 가리키는 점수가 요구하는 점수보다 작다면 min 값을 올리고 크다면 max값을 줄이는 식으로 계산합니다. 이 때 기준 점수보다 더 높은 점수의 수를 구해야 하므로 List의 전체 길이에서 구한 값을 뺀 값을 리턴해야 합니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static HashMap<String, List<Integer>> map = new HashMap<>();
    
    public int[] solution(String[] info, String[] query) {
        // map에 데이터 추가
        for(int i=0;i<info.length;i++){
            String[] arr = info[i].split(" ");
            setMap(arr, "", 0);
        }
        
        // 이분 탐색을 위한 map 데이터 정렬
        for(String key : map.keySet()){
            Collections.sort(map.get(key));
        }
        
        // 이분 탐색 진행
        int[] answer = new int[query.length];
        for(int i=0;i<query.length;i++){
            String str = query[i].replace(" and "," ");
            String[] arr = str.split(" ");
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<arr.length-1;j++)
                sb.append(arr[j]);
            
            if(map.containsKey(sb.toString()))
                answer[i] = binarySearch(sb.toString(), Integer.parseInt(arr[arr.length-1]));
            else answer[i] = 0;
        }
        
        return answer;
    }
    
    // 기준 점수를 빠르게 탐색하기 위해 이진 탐색 사용
    static int binarySearch(String key, int score){
        List<Integer> val = map.get(key);
        int min = 0;
        int max = val.size()-1;
        
        while(min <= max){
            int mid = (min+max)/2;
            if(val.get(mid) < score) min = mid+1;
            else max = mid-1;
        }
        
        // 기준값보다 더 큰 점수들만 뽑아야 하므로 val.size()에서 min값을 뺀 값을 리턴
        return val.size()-min;
    } 
    
    static void setMap(String[] arr, String str, int depth){
        if(depth == 4){
            if(!map.containsKey(str)){
                map.put(str,new ArrayList<>());
            }
            map.get(str).add(Integer.parseInt(arr[4]));
            return;
        }
        
        // 현재 조건 대입
        setMap(arr, str+arr[depth], depth+1);
        
        // - 대입
        setMap(arr, str+"-", depth+1);
    }
}