순위검색 ** (다시 풂)

사용 알고리즘: 이분탐색,

사용 언어: java

 

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 inf : info) {
            dfs(inf.split(" "), 0, "");
        }
        
        // -> 이게 없으면 효율성 테스트에서 시간초과 컷
        for (String key : map.keySet())
            Collections.sort(map.get(key));
        
        int idx = 0;
        for(String q : query) {
            String[] key = makeKey(q);
            int score = Integer.parseInt(key[1]);
            
            List<Integer> list = map.get(key[0]);
            //-> 이게 없으면 정확성 테스트에서 찾을 수 엇는 query가 들어왔을 때 런타임 에러..
            if(list == null) {
                answer[idx++] =0;
                continue;
            }
            //Collections.sort(list);
            answer[idx++] = binarySearch(list, score);
        }
        
        return answer;
    }
    
    public int binarySearch(List<Integer> list, int score) {
        int left = 0, right = list.size()-1;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            if(list.get(mid) >= score) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        
        return list.size() - left;
    }
    
    public String[] makeKey(String q) {
        String[] query = q.split(" and ");
        //0~3
        query[0] = query[0]+query[1]+query[2]+query[3].split(" ")[0];
        query[1] = query[3].split(" ")[1];
        return query;
    }
    
    public void dfs(String[] s, int dept, String key) {
        if(dept == 4) {
            if(map.containsKey(key)) {
                map.get(key).add(Integer.parseInt(s[4]));
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(Integer.parseInt(s[4]));
                map.put(key, list);
            }
            return;
        }
        
        dfs(s, dept+1, key+"-");
        dfs(s, dept+1, key+s[dept]);
    }
}

 

 

믿을 수가 없는 후기...

1. 잘 짰는데 정확성 테스트에서 런타임 에러가 난다?

 -> query가 map에서 찾을 수 없는 게 나올 수 있다.... 그걸 방지하는 코드가 필요하다

 

2. 잘 짰는데 효율성 테스트에서 시간 초과가 난다?

 -> 미리 각 key에 해당하는 list를 소팅한 후에, 이분 탐색을 돌린다.

 -> 아마도... 점수를 제외한 같은 query가 들어올 때, for문 안에서 소팅하면, 같은 list를 여러 번 소팅해야 되어서 그런 거 같다.

 

참~~나