[2021 KAKAO BLIND RECRUITMENT] 순위 검색

2021 KAKAO BLIND RECRUITMENT 순위 검색

유형

• 조합
• 이분/이진 탐색

문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다.

첫 제출시 정확성 테스트는 통과했는데, 효율성 테스트를 통과하지 못해 다른 풀이를 참고하여 코드를 수정하였다. 효율성 테스트를 통과하기 위해서 이분 탐색을 활용하는 것이 중요한 문제였다.

코드

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {

    static Map<String, List<Integer>> map;

    public static int[] solution(String[] info, String[] query) {
        // 1. info를 받아 조합가능한 모든 경우의 수를 만들고, 해당되는 조합에 점수를 매칭해준다.
        map = new HashMap<>();

        for (String applicant : info) {
            String[] spec = applicant.split(" ");
            int specSize = spec.length - 1;

            // 조건이 다 포함되는 경우부터 하나도 포함되지 않는 경우까지 만든다.
            IntStream.range(0, spec.length)
                    .forEach(r -> combination(spec, new boolean[specSize], 0, specSize, r));
        }

        // 2. 점수가 저장되어 있는 List를 정렬해준다.
        map.values().stream().forEach(Collections::sort);

        // 3. 문의 조건에 해당하는 사람들의 숫자를 배열에 담아 return
        int[] answer = new int[query.length];

        IntStream.range(0, answer.length)
                .forEach(i -> answer[i] = findMatchingPeople(query[i]));

        return answer;
    }

    private static int findMatchingPeople(String q) {
        q =  q.replace(" and ", "");
        String[] s = q.split(" ");
        String key = s[0];
        int score = Integer.parseInt(s[1]);

        if(map.containsKey(key)) {
            List<Integer> scores = map.get(key);
            return countGreaterScore(scores, score);
        } else {
            return 0;
        }
    }

    private static int countGreaterScore(List<Integer> scores, int score) {
        int start = 0, end = scores.size() - 1, mid = 0;
        while(start <= end) {
            mid = (start + end) / 2;
            if(scores.get(mid) >= score) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return scores.size() - start;
    }

    private static void combination(String[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            matchingCombToMap(arr, makeComb(arr, visited, n));
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    private static void matchingCombToMap(String[] arr, String key) {
        int score = Integer.parseInt(arr[arr.length - 1]);

        if(map.containsKey(key)) {
            map.get(key).add(score);
        } else {
            List<Integer> values = new ArrayList<>();
            values.add(score);
            map.put(key, values);
        }
    }

    private static String makeComb(String[] arr, boolean[] visited, int n) {
        String comb = "";
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                comb += arr[i];
            } else comb += "-";
        }
        return comb.trim();
    }
}