22-12-20 코딩테스트 해쉬#5 (순위 검색)

Hash와 이분탐색을 활용한 순위검색

모든 정보를 해쉬맵으로 구현

키를 통한 벨류의 정렬을 통해 비교를 쉽게 한다.(이분 탐색)

+ 문제분석

1. info를 기반으로 hashMap 생성
   각 info가 해당되는 hashmap전부 생성
2. query처리
   query조건에 맞는 지원자들의 점수 가져오기
3. 기준 점수 이상인 지원자
   query로 얻어온 정보 지원자 중 기준 점수 이상인 지원자 수 세기

import java.util.*;

class Solution08 {
    public int[] solution(String[] info, String[] query) {
        // 1. info를 기반으로 hashmap을 만든다.
        HashMap<String, ArrayList<Integer>> hashMap = new HashMap<>();

        for (String i : info) {
            String[] data = i.split(" ");
            String[] languages = { data[0], "-" };
            String[] jobs = { data[1], "-" };
            String[] exps = { data[2], "-" };
            String[] foods = { data[3], "-" };
            Integer value = Integer.parseInt(data[4]);

            for (String lang : languages)
                for (String job : jobs)
                    for (String exp : exps)
                        for (String food : foods) {
                            String[] keyData = { lang, job, exp, food };
                            String key = String.join(" ", keyData);
                            ArrayList<Integer> arr = hashMap.getOrDefault(key, new ArrayList<Integer>());

                            arr.add(value);
                            hashMap.put(key, arr);
                        }
        }

        // 2. 각 hashMap의 value를 오름차순 정렬하기
        for (ArrayList<Integer> scoreList : hashMap.values())
            scoreList.sort(null);

        // 3. query 조건에 맞는 지원자를 가져오기
        int[] answer = new int[query.length];
        int i = 0;
        for (String q : query) {
            String[] data = q.split(" and ");
            int target = Integer.parseInt(data[3].split(" ")[1]);
            data[3] = data[3].split(" ")[0];
            String key = String.join(" ", data);

            if (hashMap.containsKey(key)) {
                ArrayList<Integer> list = hashMap.get(key);
                // 4. lower-bound/하한선 찾기
                int left = 0;
                int right = list.size();
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (list.get(mid) >= target)
                        right = mid;
                    else
                        left = mid + 1;
                }

                answer[i] = list.size() - left;
            }
            i++;
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution08 sol = new Solution08();
        String[] info = { "java backend junior pizza 150", "python frontend senior chicken 210",
                "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80",
                "python backend senior chicken 50" };
        String[] query = { "java and backend and junior and pizza 100",
                "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250",
                "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150" };
        System.out.println(sol.solution(info, query));
    }
}