[프로그래머스] 순위 검색 (2021 KAKAO BLIND RECRUITMENT/Level 2)

문제 📄

문제 링크
문제가 너무 길다.. 생략

풀이 ✏️

이거 ... 그냥 일일히 비교해서 풀려고 했는데 효율성 테스트가 있는 걸 보고 어떻게 해야되나 고민했다.
가만히 쳐다보니까 그 이전에 코스 요리 메뉴 정하는 문제랑 비슷해 보여서 비슷하게 구현했다.
그리고 혹시 몰라서 구글링을 해봤는데 점수를 확인할 때 이분탐색을 사용한다고 해서... 나도 따라하다가 문득 알고리즘 수업 들을 때 이분탐색 알고리즘 활용 중에서 해당 숫자가 정렬된 배열의 몇번 째 위치에 들어가야하는 숫자인지 구하는 부분이 있었던게 갑자기 생각났다.
아무튼 .. level2 맞나요 완전탐색 + 맵 + 이분탐색 키워드만 알고 있다면 구현은 어렵지 않았는데 그걸 떠올리는게 어려웠다..

1. 모든 지원자의 지원서 항목에 대한 조합을 만든다. (점수 제외, 완전탐색 사용)
   예를들어 java backend junior pizza 150 이 정보로 지원했을 경우
   java backend junior pizza
java backend junior -
java - junior pizza
java - - -
   등의 조합이 생길 수 있다. 이러한 조합을 모두 구한 뒤, 해당 조합을 키로, 그 조합을 가질 수 있는 지원자의 점수 배열을 값으로 하는 맵을 생성한다.
2. 맵에 저장된 점수 배열을 모두 정렬한다.
3. 쿼리를 가공해서 키의 형태로 만들고, 해당 조합을 가지는 지원자의 점수 배열을 구한다.
4. 이분 탐색을 사용하여 배열에서 기준 점수에 해당하는 점수가 몇 번째 숫자인지 구한다.

코드 💻

import java.util.*;

public class Solution {
    Map<String,List<Integer>> combMap = new HashMap<>();
    List<String> comb = new ArrayList<>();

    public int[] solution(String[] info, String[] query) {
        int[] answer = {};
        // 지원자 정보로 맵 생성
        // 키 : 지원자 정보의 조합, 값: 해당 조합을 가진 지원자의 점수 목록
        for(String i : info) {
            String[] parseInfo = i.split(" ");
            comb = new ArrayList<>();
            dfs(parseInfo, 0);
        }
        // 점수 정렬
        Set<String> keys = combMap.keySet();
        for(String key : keys) {
            Collections.sort(combMap.get(key));
        }
        answer = new int[query.length];
        int idx = 0;
        for(String q : query) {
            // 쿼리 스트링 가공. and랑 - 없애고 " " 기준으로 split하면 [0]에는 정보 조합, [1]에는 기준 점수 들어
            q = q.replaceAll(" and ","");
            q = q.replaceAll("-","");
            String[] parseQuery = q.split(" ");
            String key = parseQuery[0];
            int value = Integer.parseInt(parseQuery[1]);
            int ans = 0;
            // 해당 조합이 존재하면 키값으로 점수 목록 꺼내서, 기준 점수 이상인 점수가 몇 명인지 이분탐색
            if(combMap.containsKey(key)) {
                List<Integer> valueList = combMap.get(key);
                ans = binarySearch(0,valueList.size()-1,value,valueList);
            }
            answer[idx++] = ans;
        }
        return answer;
    }

    // value에 해당하는 점수가 몇 번째 위치하는 점수인지 이분탐색
    int binarySearch(int s, int e, int value, List<Integer> valueList) {
        // s가 e를 넘어서는 순간, s의 위치는 value보다 큰 값 중 가장 작은 값의 위치이다.
        if (s > e)
            return valueList.size()-s;
        int m = (s+e)/2;
        // 찾으려는 값이 더 크면 오른쪽 탐색
        if(valueList.get(m) < value)
            return binarySearch(m+1,e,value,valueList);
        else
            return binarySearch(s,m-1,value,valueList);
    }

    void dfs(String[] info, int idx) {
        int lastIdx = info.length-1;
        if(idx == lastIdx) {
            StringBuilder sb = new StringBuilder();
            for(String c : comb) {
                sb.append(c);
            }
            String key = sb.toString();
            List<Integer> values = new ArrayList<>();
            if(combMap.containsKey(key)) {
                values = combMap.get(key);
            }
            values.add(Integer.parseInt(info[idx]));
            combMap.put(key, values);
            return;
        }
        // 현재 정보를 조합에 넣는 경우
        comb.add(info[idx]);
        dfs(info,idx+1);
        // 현재 정보를 조합에 넣지 않는 경우
        comb.remove(comb.size()-1);
        dfs(info,idx+1);
    }
}