[Programmers] 순위 검색

// 1 <= info <= 50,000
// 1 <= score <= 100,000
// 1 <= query.length <= 100,000
// 각 query에 맞는 info 갯수 구하기

// 1. hashmap을 통해 조건 노드 생성
// 2. 마지막 노드에는 점수 list 생성
// 3. 조건문을 통해 조건 충족(일치or-)인 hash 탐색
// 4. 기준 점수보다 높은 점수 찾기

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    final String[] lang = {"cpp", "java", "python"},
    job = {"backend", "frontend"},
    career = {"junior", "senior"},
    soul = {"chicken", "pizza"};
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        HashMap<String, HashMap<String, HashMap<String, HashMap<String, ArrayList<Integer>>>>> langMap = new HashMap<>();
        // 초기화
        for(String langEle : lang){
            HashMap<String, HashMap<String, HashMap<String, ArrayList<Integer>>>> jobMap = new HashMap<>();
            langMap.put(langEle, jobMap);
            for(String jobEle : job){
                HashMap<String, HashMap<String, ArrayList<Integer>>> careerMap = new HashMap<>();
                langMap.get(langEle).put(jobEle, careerMap);
                for(String careerEle : career){
                    HashMap<String, ArrayList<Integer>> soulMap = new HashMap<>();
                    jobMap.get(jobEle).put(careerEle, soulMap);
                    for(String soulEle : soul){
                        ArrayList<Integer> scoreList = new ArrayList<>();
                        careerMap.get(careerEle).put(soulEle, scoreList);
                    }
                }
            }
        }
        // info 저장
        for(String infoEle : info){
            String[] infoArr = infoEle.split(" ");
            langMap.get(infoArr[0]).get(infoArr[1]).get(infoArr[2]).get(infoArr[3]).add(Integer.parseInt(infoArr[4]));
        }
        
        for(HashMap<String, HashMap<String, HashMap<String, ArrayList<Integer>>>> jobMap : langMap.values()){
            for(HashMap<String, HashMap<String, ArrayList<Integer>>> careerMap : jobMap.values()){
                for(HashMap<String, ArrayList<Integer>> soulMap : careerMap.values()){
                    for(ArrayList<Integer> list : soulMap.values()){
                        list.sort(null);                        
                    }
                }
            }
        }
        
        for(int i = 0; i < query.length; i++){
            String queryEle = query[i];
            int scoreBlank = queryEle.lastIndexOf(" ");
            int score = Integer.parseInt(queryEle.substring(scoreBlank+1, queryEle.length()));
            String[] queryCon = queryEle.substring(0, scoreBlank).split(" and ");
            for(String langEle : lang){
                if(queryCon[0].equals("-") || queryCon[0].equals(langEle)){
                    HashMap<String, HashMap<String, HashMap<String, ArrayList<Integer>>>> jobMap = langMap.get(langEle);
                    for(String jobEle : job){
                        if(queryCon[1].equals("-") || queryCon[1].equals(jobEle)){
                            HashMap<String, HashMap<String, ArrayList<Integer>>> careerMap = jobMap.get(jobEle);
                            for(String careerEle : career){
                                if(queryCon[2].equals("-") || queryCon[2].equals(careerEle)){
                                    HashMap<String, ArrayList<Integer>> soulMap = careerMap.get(careerEle);
                                    for(String soulEle : soul){
                                        if(queryCon[3].equals("-") || queryCon[3].equals(soulEle)){
                                            ArrayList<Integer> list = soulMap.get(soulEle);
                                            int left = 0;
                                            int right = list.size()-1;
                                            int ans = list.size();
                                            while(left <= right){
                                                int mid = (left + right)/2;
                                                if(list.get(mid) >= score){
                                                    right = mid -1;
                                                    ans = mid;
                                                }else{
                                                    left = mid + 1;
                                                }
                                            }
                                            answer[i] += list.size() - ans;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return answer;
    }
}

2번 다르게 코딩했는데 둘 다 시간초과가 났다.

처음 시도는 방식이 생각이 안나지만

 두번째 시도때는 info를 score를 value로 HashMap에 넣은 뒤 query를 재귀로 돌려서 - 인경우 모든 경우를 넣게 해 map에서 찾기를 했다.  -> hash에 넣기는 문제가 없었지만 재귀로 찾기까지 돌리니 시간초과가 났다.

그래서 정답을 찾아봤는데 배워둬야 할 점은 5가지다.

1. HashMap을 이용해도 노드를 구성한다.

2. 노드에 기준 데이터를 넣은뒤 이를 따라 찾아가도록한다.

3. query를 찾을때 마지막에 get.get.get을 하기보다 중간지점을 계속 두어서 속도를 줄이기

4. ArrayList.sort(null)을 사용해 정렬하기

5. 이분탐색 : 계속해봐야겠다. 어렴풋이는 아는데 계속 잘못 작성한다.

여러번 풀어봐야하는 문제 같다.