프로그래머스-순위 검색

프로그래머스 - 순위 검색

---

문제 설명

문제 풀이

풀이 설명

처음 풀이 시, 조건을 정리 후 주어진 정보에서 찾을려고 했지만 효율성에서 실패를 맞아
주어진 정보를 정리 후 조건에 따른 결과 값을 찾도록 수정

효율성에서 또 걸려서 수정한 부분이
주어진 정보를 Map에 담고 나서 정렬을 했는지
주어진 정보를 검색할 때 이진검색을 했는지

코드 작성

        Map<String, String> infoType = new HashMap<>();
        Map<String, List<Integer>> putInfoTypeSize = new HashMap<>();
        List<String> findKeyList = new ArrayList<>();
        final String[] INFO_TYPES = new String[]{"language", "devType", "career", "food"};

        public int[] solution(String[] info, String[] query) {
            int[] answer = new int[query.length];

            for(String infoDetail : info){
                String[] splitInfoDetail = infoDetail.split(" ");

                putInfoType(splitInfoDetail[0], INFO_TYPES[0]);
                putInfoType(splitInfoDetail[1], INFO_TYPES[1]);
                putInfoType(splitInfoDetail[2], INFO_TYPES[2]);
                putInfoType(splitInfoDetail[3], INFO_TYPES[3]);

                putInfoTypeSize(splitInfoDetail[0]+splitInfoDetail[1]+splitInfoDetail[2]+splitInfoDetail[3], Integer.parseInt(splitInfoDetail[4]));
            }

            putInfoTypeSize.values().forEach(Collections::sort);

            int i = 0;
            for(String queryDetail : query) {
                findKeyList = new ArrayList<>();
                String[] splitQueryDetail = queryDetail.replaceAll("and ", "").split(" ");
                int targetGrade = Integer.parseInt(splitQueryDetail[4]);

                getQueryAllType(splitQueryDetail, "", 0);

                for(String findKey : findKeyList) {
                    List<Integer> orDefault = putInfoTypeSize.getOrDefault(findKey, new ArrayList<>());
                    int byOverGrade = findByOverGrade(orDefault, targetGrade);
                    answer[i] += byOverGrade;
                }

                i++;
            }

            for(int x : answer) {
                System.out.println("x = " + x);
            }

            return answer;
        }

        int findByOverGrade(List<Integer> findGradeList, int targetGrade){
            int start = 0;
            int end = findGradeList.size() - 1;

            while (start <= end) {
                int mid = (start + end) / 2;
                if (findGradeList.get(mid) < targetGrade)
                    start = mid + 1;
                else
                    end = mid - 1;
            }

            return findGradeList.size() - start;
        }

        void getQueryAllType(String[] splitQueryDetail, String findKey, int level){
            if(level == 4){
                findKeyList.add(findKey);
                return;
            }

            if(!isHyphen(splitQueryDetail[level])){
                findKey += splitQueryDetail[level];
                getQueryAllType(splitQueryDetail, findKey, level +1);
            }else{
                List<String> foundKeys = infoType.entrySet()
                        .stream()
                        .filter(entry -> Objects.equals(entry.getValue(), INFO_TYPES[level]))
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList());

                for (String key : foundKeys) {
                    getQueryAllType(splitQueryDetail, findKey+key, level +1);
                }
            }
        }

        void putInfoType(String key, String value){
            infoType.putIfAbsent(key, value);
        }

        void putInfoTypeSize(String key, int value){
            List<Integer> orDefault = putInfoTypeSize.getOrDefault(key, new ArrayList<>());
            orDefault.add(value);
            putInfoTypeSize.put(key, orDefault);
        }

        boolean isHyphen(String text){
            return "-". equals(text);
        }