Kakao 2021 Blind Test - Lv2. 순위검색 (Java)

문제 요약

[조건]을 만족하는 사람 중 // 코딩 테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

 

[조건]

1. 코딩 테스트 참여 개발 언어 항목 넷 중 하나를 선택한다. (cpp, java, python, -)
2. 지원 직군 항목 셋 중 하나를 선택한다. (backend, frontend, -)
3. 지원 경력 구분 항목 셋 중 하나를 선택한다. (junior, senior, -)
4. 선호하는 소울 푸드 셋 중 하나를 선택한다.  (chicken, pizza, -)

- 조건 모두를 선택할 수도 있고 조건 중 일부만 선택할 수 있다.

- '-' 는 아무 것도 선택하지 않았다는 것을 의미한다.

---

제약 조건

- info: 지원서에 입력한 4가지 정보와 획득한 코딩 테스트 점수를 하나의 문자열로 구성한 배열 (1 이상 50,000 이하)

- query: 개발팀이 궁금해하는 문의 조건 배열 (형태: "[조건] X" - X는 점수 의미, 1이상 100,000 이하) 

info	query	result
["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"]	["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"]	[1,1,1,1,2,4]

---

문제 접근 

1. 정확성만 맞춘 예 (정렬 / Binary Search 이용)

• 효율성 테스트를 통과하지 못한 이유
  • 최악의 경우 query 개수 (100,000)
  • 최악의 경우 조건을 만족하는 지원자 수 (50,000)
  • 지원자의 모든 조건 탐색 (4)
  • O(100,000 * 50,000 * 4) = O(2e10)
  • 1 억 번 계산을 1 초라 가정한다면, 1초 보다 훨씬 오랜 시간이 걸리므로 효율성 테스트 통과 X

 

// 22.05.15. - 2021 Kakao Blind - Lv2. 순위 검색

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class Kakao_2021B_lv2 {
    public static void main(String[] args) {

        String[] info = new String[]{"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 = new String[]{"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[] answer = solution(info, query);
        System.out.println(Arrays.toString(answer));
    }

    public static int[] solution(String[] info, String[] query) {

        int[] answer = new int[query.length];
        // input 분류
        ArrayList<String[]> infos = new ArrayList<>();
        for (int i = 0, size = info.length; i < size; i++) {
            String[] input = info[i].split(" ");
            infos.add(input);
        }

        // 점수에 따라 오름차순 정렬
        Collections.sort(infos, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                int item1 = Integer.parseInt(o1[4]);
                int item2 = Integer.parseInt(o2[4]);
                return item1 - item2;
            }
        });

        // 점수 배열 만들기
        int[] scores = new int[info.length];
        for (int i = 0, size = info.length; i < size; i++) {
            scores[i] = Integer.parseInt(infos.get(i)[4]);
        }

        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int q = 0, size = query.length; q < size; q++) {
            String[] order = query[q].replace(" and ", " ").split(" ");
            int score = Integer.parseInt(order[order.length - 1]);
            int cnt = 0;

            // 점수를 기준으로 시작점 찾기
            int start_point = search(scores, score);

            // query를 분석하여 조건을 만족하는 지원자가 몇 명 있는지 찾기
            for (int i = start_point, size_infos = infos.size(); i < size_infos; i++) {
                String[] each_info = infos.get(i);
                boolean flag = true;
                for (int j = 0; j < 4; j++) {
                    if (order[j].equals("-") || order[j].trim().equals(each_info[j]))
                        continue;
                    else {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                    cnt++;
            }
            answer[q] = cnt;
        }
        return answer;
    }

    // binary search 를 이용한 시작점 찾기
    public static int search(int[] scores, int criteria) {

        int left = 0, right = scores.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (criteria > scores[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

 

2. 정확성 & 효율성 통과 (HashMap/ DFS/ Binary Search 이용)

• 어떻게하면 검색 수를 줄일 수 있을까? HashMap 이용 
  
  • key: 조건의 조합 (점수 제외) = 4 * 3 * 3 * 3 = 108
  • value: 점수
  • query의 수가 조합을 만드는 경우의 수보다 훨씬 크기 때문에 최악의 경우 시간 복잡도: O(100,000)

// 22.05.15. - 2021 Kakao Blind - Lv2. 순위 검색

import java.util.*;

public class Kakao_2021B_lv2 {
    public static void main(String[] args) {

        String[] info = new String[]{"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 = new String[]{"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[] answer = solution(info, query);
        System.out.println(Arrays.toString(answer));
    }

    private static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        // info 기반 키 생성
        HashMap<String, ArrayList<Integer>> hm = new HashMap<String, ArrayList<Integer>>();
        for (int i = 0, size = info.length; i < size; i++) {
            dfs(0, "", info[i].split(" "), hm);
        }

        // 각 key별 value 오름차순 정렬
        for (String key : hm.keySet()) {
            Collections.sort(hm.get(key));
        }

        // 조건을 만족하는 지원자가 몇 명인지 찾기
        for (int i = 0, size = query.length; i < size; i++) {
            String[] each = query[i].replace(" and ", " ").split(" ");
            int criteria = Integer.parseInt(each[4]);

            StringBuilder key = new StringBuilder();
            for (int j = 0; j < 4; j++) {
                key.append(each[j].trim());
            }
            
            // 런타임 에러가 발생했던 이유: 
            // info 기반으로 hashmap의 key가 만들어지기 때문에,
            // query에서 찾고자 하는 조건이 hashmap의 key로 존재하지 않을 수 있습니다. 
            if(hm.containsKey(key)){
            	ArrayList<Integer> scores = hm.get(key.toString());
            	int search_point = search(scores, criteria);
            	answer[i] = hm.get(key.toString()).size() - search_point;
            }
        }
        return answer;
    }

    // 지원자 정보 기반 가능한 모든 키 생성
    private static void dfs(int d, String str, String[] info, HashMap<String, ArrayList<Integer>> hm) {
        if (d == 4) {
            if (!hm.containsKey(str)) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(Integer.parseInt(info[4]));
                hm.put(str, list);
            } else {
                hm.get(str).add(Integer.parseInt(info[4]));
            }
            return;
        }

        dfs(d + 1, str + info[d], info, hm);
        dfs(d + 1, str + "-", info, hm);
    }

    // binary search 를 이용한 시작점 찾기
    private static int search(ArrayList<Integer> scores, int criteria) {

        int left = 0, right = scores.size()-1;

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

---

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

공식 해설: https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설