순위 검색 - 프로그래머스(Lv. 2, 2021 KAKAO BLIND RECRUITMENT)

🎯 RGB 거리

순위검색 - Lv. 2, 2021 KAKAO BLIND RECRUITMENT

순위 검색 - 카카오 Tech 해설

---

🧐 알고리즘[접근방법]

순위 검색 문제는 Lv. 2 문제인데 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 라는 끔찍한 문구가 들어 있다.
매 쿼리 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있지만, 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없다.(정답률 :정확성 44.07%, 효율성 4.49%)
지원자들의 조건으로 만들 수 있는 모든 조건을 만들어야한다.
예를 들어 java backend junior pizza 150 인 지원자가 있으면 아래와 같이 총 16가지 경우의 수를 모두 만족시킬 수 있다.

언 어	직 군	경 력	소울 푸드	점 수
java	backend	junior	pizza	150
java	backend	junio	-	150
java	backend	-	pizza	150
java	-	junior	pizza	150
java	backend	-	-	150
java	-	junior	-	150
java	-	-	pizza	150
java	-	-	-	150
-	backend	junior	pizza	150
-	backend	junior	-	150
-	backend	-	pizza	150
-	backend	-	-	150
-	-	junior	pizza	150
-	-	junior	-	150
-	-	-	pizza	150
-	-	-	-	150

---

👨‍💻 소스

import java.util.*;

public class Main {
  
    static HashMap<String, ArrayList<Integer>> personMap;	// 지원자 모든 경우의 수가 담긴 Map
    
    public static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        
        personMap = new HashMap<String, ArrayList<Integer>>();
        
        setPerson(info);
        
        for (String key : personMap.keySet()) {
          System.out.println("key : " + key);
            Collections.sort(personMap.get(key));
        }
        
        for (int j = 0; j < query.length; j++) {
            String[] temp = query[j].split(" ");
            String key = temp[0] + temp[2] + temp[4] + temp[6];
            int score = Integer.parseInt(temp[7]);
            
            if (personMap.containsKey(key)) {
              answer[j] = countPerson(key, score);
            } else {
              answer[j] = 0;
            }
        }
        
        
        return answer;
    }
    
    public static void main(String[] args) {
        String[] info = { "java backend junior pizza 150",
                          "python frontend senior chicken 210",
                          "python frontend senior chicken 150",
                          "cpp backend senior pizza 260",
                          "java backend junior chicken 80",
                          "python backend senior chicken 50" };
        
        String[] query = { "java and backend and junior and pizza 100",
                           "python and frontend and senior and chicken 200",
                           "cpp and - and senior and pizza 250",
                           "- and backend and senior and - 150",
                           "- and - and - and chicken 100",
                           "- and - and - and - 150" };
        
        int[] result = {1, 1, 1, 1, 2, 4};
        
        solution(info, query);
        
    }
    
    // 지원자 세팅
    public static void setPerson(String[] info) {
        for (int i = 0; i < info.length; i++) {
            String[] personInfo = info[i].split(" ");
            addAllGroup(personInfo, "", 0);
        }
    }
  
  	// 지원자의 모든 경우의 수 DFS를 사용하여 구한다.
    public static void addAllGroup(String[] personInfo, String s, int depth) {
        if (4 == depth) {
            if (!personMap.containsKey(s)) {
                personMap.put(s, new ArrayList<Integer>());
            }
            personMap.get(s).add(Integer.parseInt(personInfo[4]));
            return;
        }
        
        addAllGroup(personInfo, s + "-", depth + 1);
        addAllGroup(personInfo, s + personInfo[depth], depth + 1);
    }
    
    // 쿼리에 부합되는 지원자를 이분탐색을 통해 구한다.
    public static int countPerson(String key, int score) {
        ArrayList<Integer> list = personMap.get(key);
      
        int start = 0;
        int 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;
    }
}

---

🏅 결과

정확성 테스트 2,3,4,7,13,16번이 런타임 오류가 날 경우 쿼리에 해당하는 사용자가 없는 경우 이다.

---

📖 관련 지식