[프로그래머스] 순위 검색 (JAVA)

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
개발언어는 cpp, java, python 중 하나입니다.
직군은 backend, frontend 중 하나입니다.
경력은 junior, senior 중 하나입니다.
소울푸드는 chicken, pizza 중 하나입니다.
점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
query의 각 문자열은 "[조건] X" 형식입니다.
[조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
언어는 cpp, java, python, - 중 하나입니다.
직군은 backend, frontend, - 중 하나입니다.
경력은 junior, senior, - 중 하나입니다.
소울푸드는 chicken, pizza, - 중 하나입니다.
'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

My Code

1트

항목별로 Map을 만들어 처리함
info 2차로 loop돌려서 속하는 해시맵에 add
그리고 query 또 2차 돌면서 각 항목별 map을 탐색
마지막으로 교집합인 list의 size를 리턴 배열에 넣고 리턴
결과? 쥰내 느리다.
효율성 빵점

import java.util.*;
class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] ret = new int[query.length];
        int[] scores = new int[info.length];
        
        Map<String, List<Integer>> lan = new HashMap<>();
        lan.put("cpp", new ArrayList<Integer>());
        lan.put("java", new ArrayList<Integer>());
        lan.put("python", new ArrayList<Integer>());
        lan.put("-", new ArrayList<Integer>());
        
        Map<String, List<Integer>> job = new HashMap<>();
        job.put("backend", new ArrayList<Integer>());
        job.put("frontend", new ArrayList<Integer>());
        job.put("-", new ArrayList<Integer>());
        
        Map<String, List<Integer>> work = new HashMap<>();
        work.put("junior", new ArrayList<Integer>());
        work.put("senior", new ArrayList<Integer>());
        work.put("-", new ArrayList<Integer>());
        
        Map<String, List<Integer>> food = new HashMap<>();
        food.put("chicken", new ArrayList<Integer>());
        food.put("pizza", new ArrayList<Integer>());
        food.put("-", new ArrayList<Integer>());
        
        for(int i=0 ; i<info.length ; i++) {
            String[] data = info[i].split(" ");
            
            // 개발언어
            setApps(lan, data[0], i);
            // 직군
            setApps(job, data[1], i);
            // 경력
            setApps(work, data[2], i);
            // 소울푸드
            setApps(food, data[3], i);
            // 코딩점수
            scores[i] = Integer.valueOf(data[4]);
        }
        // ex) "java and backend and junior and pizza 100"
        for(int i=0 ; i<query.length ; i++) {
            
            String[] q = query[i].replaceAll(" and","").split(" ");
            
            //print
            // for(String tmp : q) {
            //     System.out.print(tmp+"@");
            // }
            // System.out.println("");
            
            List<Integer> list = lan.get(q[0]);            
            
            for(int j=1 ; j<=3 ; j++) {
                
                //print
                // System.out.println("q["+j+"] : "+q[j]);
                // if(list==null) {
                //     System.out.println("list is null");
                //     break;
                // }
                
                
                List<Integer> require = null;
                if(j==1) require = job.get(q[j]);
                else if(j==2) require = work.get(q[j]);
                else require = food.get(q[j]);
                
                //print
                // if(require==null) {
                //     System.out.println("require is null");
                //     break;
                // }
                
                //if(list.size()==0 || require.size()==0) break;
                list = getOverlaps(list, require);
            }
            // q[4] : 코테점수
            int cnt = 0;
            for(Integer n : list) {
                if(Integer.valueOf(q[4]) <= scores[n]) cnt++;
            }
            ret[i] = cnt;
        }
        return ret;
    }
    public void setApps(Map<String, List<Integer>> hm, String d, int num) {
        hm.get(d).add(num);
        hm.get("-").add(num);
    }
    
    public List<Integer> getOverlaps(List<Integer> list, List<Integer> comp) {
        if(comp.size()>list.size()) {
            return getOverlaps(comp, list);
        }
        List<Integer> ret = new ArrayList<>();
        for(Integer l : list) {
            if(comp.contains(l)) ret.add(l);
        }
        return ret;
    }
}

2트

다른분들의 풀이 참고함.
info의 모든 케이스들에 대한 hashmap 하나만 만들어서 관리
4항목이고 "-"도 가능하니 2^2*4인 16가지의 종류가 있어서 그렇게 많지 않음.
어니 그래도 효율성 테스트에서 빵점.
1트 보단 괜찮았지만 그래도 느리다?
다른 풀이 다시 참고

import java.util.*;
class Solution {
    private Map<String, List<Integer>> hm;
    public int[] solution(String[] info, String[] query) {
        hm = new HashMap<>();
        int[] scores = new int[info.length];
        int[] ret = new int[query.length];
        
        for(int i=0 ; i<info.length ; i++) {
            String[] datas = info[i].split(" ");
            scores[i] = Integer.valueOf(datas[4]);
            setMap(datas, "", 0, i);
        }
        
        for(int i=0 ; i<query.length ; i++) {
            String[] q = query[i].replaceAll(" and","").split(" ");
            StringBuilder sb = new StringBuilder();
            sb.append(q[0]).append(q[1]).append(q[2]).append(q[3]);
            if(!hm.containsKey(sb.toString())) continue;
            
            List<Integer> list = hm.get(sb.toString());
            int cnt = list.size(), cutLine = Integer.valueOf(q[4]);
            for(int num : list) {
                if(cutLine>scores[num]) cnt--;
            }
            ret[i] = cnt;
        }
        return ret;
    }
    
    public void setMap(String[] datas, String data, int len, int num) {
        if(len==4) {
            insertMap(data, num);
            return;
        }
        setMap(datas, data+datas[len], len+1, num);
        setMap(datas, data+"-", len+1, num);
        return;
    }
    
    public void insertMap(String data, int num) {
        if(!hm.containsKey(data)) {
            hm.put(data, new ArrayList<Integer>());
        }
        hm.get(data).add(num);
    }
    
}

3트

score 이분법...
원래는 info의 index값으로 list에 넣고
마지막에 스코어들이 들어있는 score 배열과 커트라인 비교하여 카운트하는거였는데, 처음부터 점수를 넣고 그다음 sort하고 이분법을 하면 더 효율적이네..
어쨌든 정답이면 뭐하나 효율적이지 못하게 풀었었는데...
또 하나 배운다

import java.util.*;
class Solution {
    private Map<String, List<Integer>> hm;
    public int[] solution(String[] info, String[] query) {
        hm = new HashMap<>();
        //int[] scores = new int[info.length];
        int[] ret = new int[query.length];
        
        for(int i=0 ; i<info.length ; i++) {
            String[] datas = info[i].split(" ");
            //scores[i] = Integer.valueOf(datas[4]);
            setMap(datas, "", 0, Integer.valueOf(datas[4]));
        }
        
        // 점수 정렬
        for(Map.Entry<String, List<Integer>> e : hm.entrySet()) {
            List<Integer> scores = e.getValue();
            Collections.sort(scores);
        }
        
        for(int i=0 ; i<query.length ; i++) {
            String[] q = query[i].replaceAll(" and","").split(" ");
            StringBuilder sb = new StringBuilder();
            //sb.append(q[0]).append(q[1]).append(q[2]).append(q[3]);
            sb.append("");
            if(!q[0].equals("-")) sb.append(q[0]);
            if(!q[1].equals("-")) sb.append(q[1]);
            if(!q[2].equals("-")) sb.append(q[2]);
            if(!q[3].equals("-")) sb.append(q[3]);
            String s = sb.toString();
            
            if(!hm.containsKey(s)) continue;
            
            List<Integer> score = hm.get(s);
            int cutLine = Integer.valueOf(q[4]);
            int start = 0, end = score.size()-1;
            
            // 이분탐색
            while(start<=end) {
                int mid = (start+end)/2;
                if(score.get(mid) < cutLine) {
                    start = mid+1;	
                } else {
                    end = mid-1;
                }
            }
            
            ret[i] = score.size()-start;
        }
        return ret;
    }
    
    public void setMap(String[] datas, String data, int len, int score) {
        if(len==4) {
            insertMap(data, score);
            return;
        }
        setMap(datas, data, len+1, score);
        setMap(datas, data+datas[len], len+1, score);
        return;
    }
    
    public void insertMap(String data, int score) {
        //System.out.println(data);
        if(!hm.containsKey(data)) {
            hm.put(data, new ArrayList<Integer>());
        }
        hm.get(data).add(score);
    }
    
}