[프로그래머스] 순위 검색 - Java

문제 링크

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

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

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

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

알고리즘: 구현, 이분 탐색

풀이

먼저 단순하게 생각했을 때 query마다 info를 순차 탐색한다면 50,000 * 100,000으로 효율성을 절대 통과할 수 없다. 다른 방법을 찾아야 하는데
내가 생각한 방식은 이렇다.

조건의 경우의 수를 따져보면 개발언어 4가지 ("-" 포함) 직군 3가지, 경력 3가지, 소울푸드 3가지로 총 108개로 매우 적다는 것을 확인할 수 있다. info의 각 조건에 맞는 list에 코딩테스트 점수만 넣어준다.

예를 들면 java backend junior pizza라면
1. java backend junior pizza
2. java backend junior -
3. java backend - pizza
.... (16가지) 이런 식으로 각 조건에 해당하는 list에 코딩테스트 점수를 넣는다.

그리고 위 작업이 끝났다면 이제 query를 순차 탐색한다. 탐색하면서 해당 조건에 list에서 이분 탐색을 활용해 몇 명이 해당 조건을 만족하는지 찾아낸다.
(여기서 이분 탐색은 정렬된 리스트에서 사용할 수 있기 때문에 info를 먼저 코딩테스트 점수를 기준으로 오름차순 정렬 후에 각 조건에 해당하는 list에 코딩테스트 점수를 넣어준다. 그러면 자연스럽게 낮은 점수부터 list에 들어가게 됨)

시간 복잡도는

1. 조건에 맞는 list에 점수를 넣는 경우 -> 16 * 50,000
2. 쿼리에 맞는 사람을 찾는 경우 -> 100,000 * (log (x <= 50000))

소스 코드

import java.util.*;
class Solution {
    static ArrayList<Integer>[][][][] info_list = new ArrayList[4][3][3][3];
    static ArrayList<Integer> result = new ArrayList<>();
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        Arrays.sort(info, (a, b) -> {
            String[] split_a = a.split(" ");
            String[] split_b = b.split(" ");
            int dif = Integer.parseInt(split_a[4]) - Integer.parseInt(split_b[4]);
            if(dif <= 0) return -1;
            else return 1;
        });
        for(int i=0; i<info.length; i++) {
            String[] split_info = info[i].split(" ");
            DFS(find_index(split_info[0]), find_index(split_info[1]), find_index(split_info[2]), find_index(split_info[3]), Integer.parseInt(split_info[4]));
        }
        //탐색
        for(int i=0; i<query.length; i++) {
            String[] split_query = query[i].split(" ");
            answer[i] = find_answer(info_list[find_index(split_query[0])][find_index(split_query[2])][find_index(split_query[4])][find_index(split_query[6])], Integer.parseInt(split_query[7]));
        }
        return answer;
    }
    
    static int find_answer(ArrayList<Integer> list, int value) {
        if(list == null) return 0;
        int min = 0;
        int max = list.size() - 1;
        while(min <= max) {
            int mid = (min + max) / 2;
            if(list.get(mid) >= value) max = mid - 1;
            else min = mid + 1;
        }
        return (list.size() - 1) - min + 1;
    }
    
    static void DFS(int i1, int i2, int i3, int i4, int score) {
        if(result.size() == 4) {
            int ind1 = result.get(0) == 1 ? i1 : 0;
            int ind2 = result.get(1) == 1 ? i2 : 0;
            int ind3 = result.get(2) == 1 ? i3 : 0;
            int ind4 = result.get(3) == 1 ? i4 : 0;
            if(info_list[ind1][ind2][ind3][ind4] == null) info_list[ind1][ind2][ind3][ind4] = new ArrayList<>();
            info_list[ind1][ind2][ind3][ind4].add(score);
            return;
        }
        for(int i=0; i<2; i++) {
            //0은 -, 1은 선택
            result.add(i);
            DFS(i1, i2, i3, i4, score);
            result.remove(result.size()-1);
        }
    }
    
    static int find_index(String item) {
        if(item.equals("cpp") || item.equals("backend") || item.equals("junior") || item.equals("chicken")) return 1;
        else if(item.equals("java") || item.equals("frontend") || item.equals("senior") || item.equals("pizza")) return 2;
        else if(item.equals("python")) return 3;
        return 0; // "-"
    }
}