[프로그래머스 Lv.2] 순위 검색

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

문제 설명

지원자가 지원서에 입력한 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점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

풀이

To-Do 리스트

1. 지원자 리스트와 채용 리스트를 생성.
2. 채용리스트에 지원자가 충족되면 1씩 더함.

결과

import java.util.*;

class Developer {
    String language;
    String subject;
    String career;
    String soulFood;
    int score;
    
    public Developer(String language, String subject, String career, String soulFood, int score){
        this.language = language;
        this.subject = subject;
        this.career = career;
        this.soulFood = soulFood;
        this.score = score;
    }
    
    @Override
    public String toString(){
        return "["+this.language+", "+this.subject+", "+this.career+", "+this.soulFood+", "+this.score+"]";
    }
}

class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        int k = 0;
        
        List<Developer> list = new ArrayList<>();
        List<Developer> quelist = new ArrayList<>();
        
        for(String p: info){
            String[] srr = p.split(" ");
            Developer dp = new Developer(srr[0],srr[1],srr[2],srr[3],Integer.parseInt(srr[4]));
            list.add(dp);
        }
        
        for(String q : query){
            String[] srr = q.replaceAll("and ","").split(" ");
            Developer dp = new Developer(srr[0],srr[1],srr[2],srr[3],Integer.parseInt(srr[4]));
            quelist.add(dp);
        }
        
        for(Developer h: quelist){
            //System.out.println(h.toString());
            for(Developer v: list){
                if((h.language.equals(v.language) || h.language.equals("-"))
                  && (h.subject.equals(v.subject) || h.subject.equals("-"))
                  && (h.career.equals(v.career) || h.career.equals("-"))
                  && (h.soulFood.equals(v.soulFood) || h.soulFood.equals("-"))
                  && h.score <= v.score){
                    answer[k]++;
                    //System.out.println(">"+v.toString());
                }
            }
            k++;
        }
        
        return answer;
    }
}

알게 된 점

💥 효율성 테스트 0점.
💥 지원자를 기준으로 만들 수 있는 경우의 수를 map형태로 저장.
💥 map정렬시에 일일히 정렬하는 것보다 한번에 정리하면 시간단축이 가능.
💥 이분법으로 스코어보다 높은 사람의 수를 구함.

import java.util.*;

class Solution {
    static Map<String, List<Integer>> map = new HashMap<>();
    public void numberofcase(String[] srr, String str, int cnt){
        if(cnt == 4){
            if(!map.containsKey(str)){
                map.put(str, new ArrayList<>());
            }
            map.get(str).add(Integer.parseInt(srr[4]));
            return;
        }
        
        numberofcase(srr, str+"-", cnt+1);
        numberofcase(srr, str+srr[cnt], cnt+1);
    }
    
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        
        for(int i = 0; i < info.length; i++){
            String srr[] = info[i].split(" ");
            numberofcase(srr,"",0);
        }
        
        for(String key: map.keySet()){
            Collections.sort(map.get(key));
        }
        
        for(int i = 0; i < query.length; i++){
            String[] t = query[i].replaceAll(" and ","").split(" ");
            if(map.get(t[0]) != null){
                List<Integer> list = map.get(t[0]);
                int s = 0;
                int e = list.size()-1;
                while(s <= e){
                    int m = (s+e)/2;
                    if(list.get(m) < Integer.parseInt(t[1])){
                        s = m + 1;
                    }else {
                        e = m - 1;
                    }
                }
                answer[i] = list.size()-s;
            }
        }
        
        return answer;
    }
}