[프로그래머스 / Level2] 순위 검색 (Java)

문제 보기

문제에서 배열의 길이가 너무 길다면 이진탐색을 생각해보자. 근데 이게 레벨2라고?

풀이

• 특정 질문이 포함되거나 포함되지 않을 수 있기 때문에 DFS를 사용하여 map에 모든 경우의 수 넣어주기
• 그냥 배열을 순차적으로 탐색하여 답을 구하면 시간 초과가 나오기 때문에 map의 value를 오름차순으로 정렬한 뒤 이진탐색 사용
  
  
• 모든 평가기준에 적용할 수 있도록 지원자들의 정보를 반복문을 돌며 split()으로 지원자의 정보를 쪼갠다.
• 쪼갠 지원자의 정보 배열로 DFS를 돌며 특정 질문이 포함되지 않는 경우를 고려하여 정보 혹은 "-"를 넣어 문자열을 완성 후 map에 정보들을 key로, 점수를 리스트인 value에 넣어준다.
• 예를 들면 아래와 같은 예시들을 map에 저장하는 것이다.
  • key: "----", value: 150
  • key: "java---", value: 150
  • key: "-frontend-chicken", value: 150
  • key: "javabackendjuniorpizza", value: 150
• 모두 저장했으면 이진탐색을 활용하기 위하여 map의 value들을 정렬한다.
• 마지막으로 문의조건들을 반복문을 돌며 문의조건에 일치하는 지원자의 수를 이진탐색으로 찾아 answer의 현재 인덱스에 넣어주고, 일치하는 지원자가 없으면 0을 넣어준다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

class Solution {

    HashMap<String, List<Integer>> map = new HashMap<>();

    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        for (int i = 0; i < info.length; i++) {
            String[] infos = info[i].split(" ");
            dfs(infos, "", 0);
        }

        for (String key : map.keySet()) {
            Collections.sort(map.get(key));
        }

        for (int i = 0; i < query.length; i++) {
            String fixedQuery = query[i].replaceAll(" and ", "");
            String[] questions = fixedQuery.split(" ");
            if (map.containsKey(questions[0])) {
                answer[i] = binarySearch(questions[0], Integer.parseInt(questions[1]));
            } else {
                answer[i] = 0;
            }
        }

        return answer;
    }

    public void dfs(String[] infos, String key, int depth) {
        if (depth == 4) {
            if (!map.containsKey(key)) {
                List<Integer> value = new ArrayList<>();
                map.put(key, value);
            }
            map.get(key).add(Integer.parseInt(infos[4]));
            return;
        }
        dfs(infos, key + "-", depth + 1);
        dfs(infos, key + infos[depth], depth + 1);
    }

    public int binarySearch(String key, int score) {
        List<Integer> scores = map.get(key);
        int left = 0;
        int right = scores.size() - 1;

        while(left <= right) {
            int mid = (left + right) / 2;
            if(scores.get(mid) < score) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return scores.size() - left;
    }
}