[72412] 순위 검색

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

코딩테스트 연습 - 순위 검색

 

문제 해결 방법

query를 하나씩 보면서 info배열을 탐색하면 당연히 시간 초과가 날 거 같아서 info배열을 먼저 보면서 HashMap에 가능한 조합과 점수를 넣어줬다.

 

info가 "java backend junior pizza 150" 라면
javabackendjuniorpizza
-backendjuniorpizza
java-juniorpizza
javabackend-pizza
javabackendjunior-
--juniorpizza
java--pizza
.
.
.
등등의 query에 검색된다.
dfs를 이용해 모두 hashmap에 넣어준다.

 

첫 번째 시도

import java.util.*;

class Solution {
    static HashMap<String, ArrayList<Integer>> map;
    public int[] solution(String[] info, String[] query) {
        map = new HashMap<>();
        
        for(int i = 0; i < info.length; i++) {
            String[] infos = info[i].split(" ");
            dfs(0, "", infos);
        }

        int[] answer = new int[query.length];
        
        for(int i = 0; i < query.length; i++) {
            String[] filter = query[i].replace("and ", "").split(" ");
            String queryString = "";
            for(int j = 0; j < 4; j++) {
                queryString += filter[j];
            }

            int score = Integer.parseInt(filter[4]);
            if(!map.containsKey(queryString)) continue;
            ArrayList<Integer> list = map.get(queryString);
            int cnt = 0;
            for(int j = 0; j < list.size(); j++) {
                if(list.get(j) >= score) cnt++;
            }
            answer[i] = cnt;
        }
        return answer;
    }
    public void dfs(int cnt, String str, String[] infos) {
        if(cnt == 4) {
            int score = Integer.parseInt(infos[4]);
            if(!map.containsKey(str)) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                map.put(str, list);
            } else map.get(str).add(score);
            
            return;
        }
        
        dfs(cnt + 1, str + infos[cnt], infos);
        dfs(cnt + 1, str + "-", infos);
    }
}

정확성은 통과했지만 효율성을 하나도 통과하지 못했다..

 

두 번째 시도

score 비교를 위해 binary search를 추가했다.

import java.util.*;

class Solution {
    static HashMap<String, ArrayList<Integer>> map;
    public int[] solution(String[] info, String[] query) {
        map = new HashMap<>();
        
        for(int i = 0; i < info.length; i++) {
            String[] infos = info[i].split(" ");
            dfs(0, "", infos);
        }

        int[] answer = new int[query.length];
        
        for(int i = 0; i < query.length; i++) {
            String[] filter = query[i].replace("and ", "").split(" ");
            String queryString = "";
            for(int j = 0; j < 4; j++) {
                queryString += filter[j];
            }

            int score = Integer.parseInt(filter[4]);
            if(!map.containsKey(queryString)) continue;
            ArrayList<Integer> list = map.get(queryString);
            answer[i] = list.size() - bsearch(list, score);
        }
        return answer;
    }
    public void dfs(int cnt, String str, String[] infos) {
        if(cnt == 4) {
            int score = Integer.parseInt(infos[4]);
            if(!map.containsKey(str)) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                map.put(str, list);
            } else map.get(str).add(score);
            
            return;
        }
        
        dfs(cnt + 1, str + infos[cnt], infos);
        dfs(cnt + 1, str + "-", infos);
    }
    
    public int bsearch(ArrayList<Integer> list, int score) {
        Collections.sort(list);
        int min = 0;
        int max = list.size() - 1;
        while(min <= max) {
            int mid = (min + max) / 2;
            if(list.get(mid) < score) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return min;
    }
}

 

ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

 

세 번째 시도

query를 볼 때마다 정렬하는 게 아니라 HashMap을 완성하고, query를 보기 전에 정렬을 해줬다.

import java.util.*;

class Solution {
    static HashMap<String, ArrayList<Integer>> map;
    public int[] solution(String[] info, String[] query) {
        map = new HashMap<>();
        
        for(int i = 0; i < info.length; i++) {
            String[] infos = info[i].split(" ");
            dfs(0, "", infos);
        }

        map.forEach((key, value) -> {
            Collections.sort(value);    
        });
        
        int[] answer = new int[query.length];
        
        for(int i = 0; i < query.length; i++) {
            String[] filter = query[i].replace("and ", "").split(" ");
            String queryString = "";
            for(int j = 0; j < 4; j++) {
                queryString += filter[j];
            }

            int score = Integer.parseInt(filter[4]);
            if(!map.containsKey(queryString)) continue;
            ArrayList<Integer> list = map.get(queryString);
            answer[i] = list.size() - bsearch(list, score);
        }
        return answer;
    }
    public void dfs(int cnt, String str, String[] infos) {
        if(cnt == 4) {
            int score = Integer.parseInt(infos[4]);
            if(!map.containsKey(str)) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                map.put(str, list);
            } else map.get(str).add(score);
            return;
        }
        
        dfs(cnt + 1, str + infos[cnt], infos);
        dfs(cnt + 1, str + "-", infos);
    }
    
    public int bsearch(ArrayList<Integer> list, int score) {
        int min = 0;
        int max = list.size() - 1;
        while(min <= max) {
            int mid = (min + max) / 2;
            if(list.get(mid) < score) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return min;
    }
}

 

!!!!!!!!!!!!