[Algorithm] 6월 24일 알고리즘 연습 - 에이젠

 

 

내풀이(1) : 효율성테스트를 통과하지 못함.

수많은 사람들의 점수를 일일이 검사하면서 비효율 발생 -> 참고한 코드를 통해 이분탐색을 통해 해결하는 것을 확인.

듣기로 이문제가 LEVEL2중 상위권 문제라고 많이 언급하는 것 같다.

이 이상의 수준은 두개 이상의 알고리즘을 사용하는 경우가 많을 것같다.

class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] answer = {};
        answer = new int[query.length];
        ArrayList<Person> arr = new ArrayList<Person>();
        //생성
        for(String str : info){
            String[] input = str.split(" ");
            //사람 생성
            //input[0],input[1],input[2],input[3],input[4]
            arr.add(
                new Person(
                    input[0],input[1],input[2],input[3],Integer.parseInt(input[4])
                )
            );
        }
        //검사
        for(int j = 0; j < query.length; j++){
            String[] temp = query[j].split(" ");
            //  0        2           4         6     7
            //java and backend and junior and pizza 100
            //cpp  and  -      and senior and pizza 250
            for(int i = 0; i < arr.size(); i++){
                if(
                    arr.get(i).language.equals(temp[0]) ||
                    temp[0].equals("-")
                  ){
                    if(
                    arr.get(i).position.equals(temp[2]) ||
                        temp[2].equals("-")
                    ){
                        if(
                            arr.get(i).career.equals(temp[4]) ||
                            temp[4].equals("-")
                        ){ 
                            if(
                                arr.get(i).soulFood.equals(temp[6]) ||  
                                temp[6].equals("-")
                            ){
                                if(    
                                    arr.get(i).point >= Integer.parseInt(temp[7]) ||
                                    temp[7].equals("-")
                                ){
                                    answer[j] = answer[j] + 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        
        
        return answer;
    }
}

class Person {
    String language = "";//언어
    String position = "";//직군
    String career = "";
    String soulFood = "";
    int point = 0;
    
    public Person(String language, String position, String career, String soulFood, int point){
        this.language = language;
        this.position = position;
        this.career = career;
        this.soulFood = soulFood;
        this.point = point;
    }
}

참고한 풀이

class Solution {
    static HashMap<String, List<Integer>> map;
 
    public static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        map = new HashMap<String, List<Integer>>();
 
        for (int i = 0; i < info.length; i++) {
            String[] p = info[i].split(" ");
            makeSentence(p, "", 0);
        }
 
        for (String key : map.keySet())
            Collections.sort(map.get(key));
 
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll(" and ", "");
            String[] q = query[i].split(" ");
            answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
        }
 
        return answer;
    }
 
    // 이분 탐색
    private static int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        int start = 0, end = list.size() - 1;
 
        while (start <= end) {
            int mid = (start + end) / 2;
            if (list.get(mid) < score)
                start = mid + 1;
            else
                end = mid - 1;
        }
 
        return list.size() - start;
    }
 
    // info가 포함될 수 있는 문장
    private static void makeSentence(String[] p, String str, int cnt) {
        if (cnt == 4) {
            if (!map.containsKey(str)) {
                List<Integer> list = new ArrayList<Integer>();
                map.put(str, list);
            }
            map.get(str).add(Integer.parseInt(p[4]));
            return;
        }
        makeSentence(p, str + "-", cnt + 1);
        makeSentence(p, str + p[cnt], cnt + 1);
    }
}

https://jisunshine.tistory.com/153

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