[프로그래머스_카카오]순위검색

풀이 생각

• 완전탐색 → 불가능. 50000 x 100000 → 500억이다

• 따라서 든 생각 1. Hash or Matrix(다차원 배열 형태) 2. 이진탐색(lower bound)

• 문제를 보고 위의 생각은 바로들었는데 Hash로 삽질 했다. 다른 분들은 Hash로 잘 푸시던데 나는 머리에 혼란이 오고 삽질을 몇시간이나 하게되어 큰 스트레스가 된 덕분에 Matrix로 풀이를 바꿔보았다. (애매하게 안 풀리는게 여전히 큰 스트레스고 극복하지 못해 큰일이다...)

1. 조건 별로 Map을 생성한다면? 언어Map, 직군Map (X)
   ==> and로 다른 조건과 함께 하는 것을 못 찾는다. (X)

2. Matrix어떤가

• Matrix[언어][분야][경력][선호푸드]
  2-1 . 이 Matrix에 List를 저장하여 → 점수를 저장한다.
• 따라서, X점수 이상의 사람들을 구하기 위해서는 또다시 탐색이 필요하다. 그렇다고 List를 전체 탐색하겠는가? --> O(n)을 모두 탐색하는 것을 반복하다보면 결국은 또다시 완전탐색과 비슷해진다.
• 차라리 정렬 (O(nlogn))을 한 후, lower bound(O(logn))을 찾는 것이 나을 것이다.
• 💥💥💥쿼리에서 "-"가 나오면, Matrix를 사용하고 있기 때문에 해당 차원에서는 전체를 돌면서, 각각에서 lowerbound를 구하여 각각에서의 인원을 모두 합산해주면 된다.
  • 그런데 이를 구현하는게 또 최선의 방법을 생각하지 못하겠었다.
  • 그래서 , Matrix[a][b][c][d] 가 있다고 했을 때, a의 범위의 시작과 끝을 가리키는 as,ae를 둔다. b,c,d에 대해서도 같은 것을 반복하였다.

3. 카카오 메뉴얼 문제처럼 이것도 아예 조합을 먼저 다 만들어 놓아볼까???

• 점수 빼고, 조건만 조합한다면? "0002"라던가 "---2"라던가 -> Hash에 저장하고
• 또.. 그다음에 는 lower bound를 통하여 개수를 구하는 것 (정렬도 필요)/
• Hash 를 사용하더라도, 점수 때문에 탐색이 필요하다
  • 탐색을 → 이진탐색을 사용할 수 있지 않을까? → lower bound index를 찾는 방식으로 할 수 있지 않을까
  • 그런데 이를 위해서는.. 정렬하는 것도 필요하다.
• Hash로 변환하는 과정이 너무 복잡했다. (메뉴 리뉴얼 문제를 풀고 이 문제를 푸느라, 주어진 문장을 다른 Hash value로 변환하려고 하는 과정을 생각해버렸다. 매우 오랜 시간이 걸렸고 머리속이 꼬여서 제대로 풀지 못했다.)

• 2번을 사용해보자.

import java.util.*;
class Solution {
    public Map<String,Integer> info_map[]=new HashMap[4];
    public ArrayList<Integer> matrix[][][][] = new ArrayList[3][2][2][2];
    public void setting(String[] info, String[] query){
        for(int i=0;i<4;i++)
            info_map[i] = new HashMap<String,Integer>();
        info_map[0].put("cpp",0);
        info_map[0].put("java",1);
        info_map[0].put("python",2);
        info_map[0].put("-",-1);
        info_map[1].put("backend",0);
        info_map[1].put("frontend",1);
        info_map[1].put("-",-1);
        info_map[2].put("junior",0);
        info_map[2].put("senior",1);
        info_map[2].put("-",-1);
        info_map[3].put("chicken",0);
        info_map[3].put("pizza",1);
        info_map[3].put("-",-1);
        for(int i=0;i<3;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    for(int m=0;m<2;m++)
                        matrix[i][j][k][m]= new ArrayList<>();
                }
            }
        }
    }
    // info 쪼개서  matrix 세팅하기 O(n)
    public void makeMatrix(String[] info){
        for(String s:info) {
            String[] datas = s.split(" ");
            matrix[info_map[0].get(datas[0])][info_map[1].get(datas[1])][info_map[2].get(datas[2])][info_map[3].get(datas[3])]
                    .add(Integer.parseInt(datas[4]));
        }
    }
    public int[] solution(String[] info,String[] query){
        int[] answer ={};
        setting(info,query);
        makeMatrix(info);
        // 각 리스트들을 모두 정렬시켜야 한다. (nlogn)
        for(int i=0;i<3;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    for(int m=0;m<2;m++)
                        Collections.sort(matrix[i][j][k][m]);
                }
            }
        }
        answer = parseQuery(query);
        return answer;
    }
    // query 쪼개서 쿼리별로 돌리기 
    public int[] parseQuery(String[] query){
        int[] answer = new int[query.length];
        String[] temp;
        String[] datas = new String[5];
        int i=0,j=0;
        int[] idxes = new int[4];
        int target=0,count=0,qcnt=0;

        for(String q:query){
            count=0; // target이상의 점수를 가진 사람 count
            // 하나의 쿼리에 대해 String[5]의 datas를 생성
            temp = q.split(" and ");
            for(i=0;i< temp.length-1;i++)datas[i]=temp[i];
            temp = temp[temp.length-1].split(" ");
            for(j=0;j<temp.length;j++)datas[i++]=temp[j];
            target = Integer.parseInt(datas[4]);
            for(i=0;i<4;i++){
                idxes[i]=info_map[i].get(datas[i]);
            }
            int as=0,ae=0,bs=0,be=0,cs=0,ce=0,ds=0,de=0;
            if(idxes[0]==-1){
                as=0;ae=3;
            }else{
                as=idxes[0];
                ae=idxes[0]+1;
            }
            if(idxes[1]==-1){
                bs=0;be=2;
            }else{
                bs=idxes[1];
                be=idxes[1]+1;
            }
            if(idxes[2]==-1){
                cs=0;ce=2;
            }else{
                cs=idxes[2];
                ce=idxes[2]+1;
            }
            if(idxes[3]==-1){
                ds=0;de=2;
            }else{
                ds=idxes[3];
                de=idxes[3]+1;
            }
            // index가 -1이면 -> for문을 다 돌아야 한다.
            for(int a=as;a<ae;a++){
                for(int b=bs;b<be;b++){
                    for(int c=cs;c<ce;c++){
                        for(int d=ds;d<de;d++){
                            int idx=lower_bound(matrix[a][b][c][d],target);
                            count+=(matrix[a][b][c][d].size()-idx);
                        }
                    }
                }
            }
            answer[qcnt++]=count;
        }
        return answer;
    }
    public int lower_bound(ArrayList<Integer> list,int target){
        int left =0,right = list.size();
        int mid =0;
        while(left<right){
            mid = (left+right)/2;
            if(list.get(mid)>=target)right=mid;
            else left = mid+1;
        }
        return right;
    }
}

테스트 1 〉 통과 (1.05ms, 59.8MB)
테스트 2 〉 통과 (1.25ms, 71.4MB)
테스트 3 〉 통과 (9.77ms, 73MB)
테스트 4 〉 통과 (24.58ms, 76.1MB)
테스트 5 〉 통과 (39.54ms, 80.3MB)
테스트 6 〉 통과 (13.09ms, 76.6MB)
테스트 7 〉 통과 (33.98ms, 79.3MB)
테스트 8 〉 통과 (26.33ms, 80MB)
테스트 9 〉 통과 (23.86ms, 76.3MB)
테스트 10 〉 통과 (13.92ms, 82.3MB)
테스트 11 〉 통과 (17.85ms, 77.2MB)
테스트 12 〉 통과 (14.55ms, 76.1MB)
테스트 13 〉 통과 (21.77ms, 80.9MB)
테스트 14 〉 통과 (12.15ms, 62.4MB)
테스트 15 〉 통과 (18.26ms, 76.8MB)
테스트 16 〉 통과 (26.81ms, 62.6MB)
테스트 17 〉 통과 (16.65ms, 61.8MB)
테스트 18 〉 통과 (14.61ms, 62.8MB)
효율성 테스트
테스트 1 〉 통과 (651.75ms, 210MB)
테스트 2 〉 통과 (607.80ms, 248MB)
테스트 3 〉 통과 (850.87ms, 220MB)
테스트 4 〉 통과 (849.07ms, 243MB)