[Programmers] 2021 KAKAO BLIND RECRUITMENT 순위 검색 - JAVA

문제

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

 

풀이 과정

처음에는 info와 query를 하나씩 비교하여 조건을 만족하는 지원자를 찾는 방식으로 접근했었는데, 시간초과로 실패했다.

해결 방법이 마땅히 떠오르지 않아, 정답 풀이를 참고해보았다.

 

문제 접근 방식

1. 모든 경우의 조건을 Map에 관리

하나의 지원자 정보가 만들 수 있는 조건을 모두 생성하여 Map에 관리한다.

• key: 조건
• value: 점수(리스트)

예시: java backend junior pizza 150 => 총 16개의 조합을 생성

key: "javabackendjuniorpizza", value: [150]
key: "javabackendjunior-", value: [150]
key: "java-juniorpizza", value: [150]
...
key: "----", value: [150]

 

 for (String str : info) {
    String[] split = str.split(" ");
    dfs(split, "", 0);
}

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

 

2. 정렬

• 모든 점수를 오름차순 정렬한다.

 for (List<Integer> scores : map.values()) {
    Collections.sort(scores);
}

 

3. 이분탐색

query에 부합하는 지원자 수를 찾기 위해 map을 탐색하는데, 처리 시간을 단축하기 위해 이분 탐색을 사용한다.

• 하나의 query씩 처리한다.
• query 문자열에서 " and " 제거 후 조건과 점수를 분리한다.
• map에 해당 조건의 리스트를 찾아 점수가 score 이상인 사람 수를 이분 탐색으로 계산한다. 

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

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

 

 

코드

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();

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

        for (List<Integer> scores : map.values()) {
            Collections.sort(scores);
        }

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

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

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