문제

문제 링크

데이터를 주고 쿼리를 처리해보라는 문제다.

단순하게 문자열로 잘라서 갯수를 세어보기만하면 될 줄 알았다.

구현

컬럼수만큼 배열을 만들고 카운트 해주는 식으로 도전했다.

// 간단한 처리를 위해 문자를 각각 012로 매칭함.
int[][][][][] data;

data를 모두 채우고나서가 문제가 되었다.

예를들어
100점 이상인 모든 데이터를 얻기위해서는 단순하게 생각한다면 순차순회하면 될것이다.
그러나 언뜻 생각해봐도 매우 비효율적이다.

다음과 같이 각 인덱스마다 데이터의 갯수가 있다고 생각해보자
0 1 2 3 4 5 6 7 8 9 ...
0 0 1 0 0 2 0 0 0 0 ...

그러면 2 이상인 데이터를 찾기위해서 [2,data.length()] 까지를 구해야하는데 중간에 0인 데이터가 끼어있다면 골치가 아프다.
(잠시 세그먼트 트리를 사용해야할까 싶었는데 모든 조합의 트리를 만드는건 너무 메모리를 많이 쓰고 구현도 꽤 힘들거같았다.)

그래서 배열에 append 하는 방식으로 데이터를 넣어야함을 알게되었다.
그러면 [2,5,5,10,15,20] 같이 데이터가 존재할때 5에 가장 작은 인덱스를 구하면 5이상인 데이터 갯수를 알수있었다.

이는 이진탐색을 통해 가능하다.

(java에서는 다중 배열을 사용할때 정렬을 하려면 각 차원마다 비교해주어야한다.
그래서 다중 배열을 사용하는 대신에 String으로 변환해 Map으로 치환해주었다.)

시간복잡도

• • junior pizza 100 이라는 데이터가 들어온다면
    처음부터 - 칸을 고려한 모든 경우의 수를 먼저 넣어줄지
    아니면 나중에 쿼리를 처리할때 여러번 계산해줄지 선택할수있다.

쿼리를 여러번 계산

먼저 입력 데이터를 map으로 처리하는데는 입력 데이터 갯수만큼 시간이든다. (5만)

쿼리를 - 가 섞여있는데 이는 cpp,java,python처럼 다지선택을 모두 처리해야해서 각 카디널리티만큼 곱하기가 들어간다.
그러면 3x2x2x2x쿼리수(10만)큼 쿼리를 처리해야한다.
=> 24x10만 = 240만

각 쿼리는 이진트리를 통해 처리하므로
리스트 길이를 n(최대 5만)이라고하면 로그 n(최대 16)만큼 시간이 들것이다.

즉 5x10^4x240x10^4x16 = 19200x10^8 (19200초)
(이 방식으로 풀었는데도 효율성 테스트를 통과하였다.)

가능한 모든 입력을 넣어줌

근데 처음에 입력 데이터 처리할때 중복마저 다 넣어준다면
5만x24 만큼 시간이 들지만
쿼리를 딱 한번만 처리하며 된다. 10만x16
그러면 최종 시간복잡도는 5x10^4x10x10^4x16 = 800x10^8 (800초)가 된다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        Map<String, List<Integer>> map=new HashMap<>();
        setMap(map,info);
        sortMap(map);
        int[] ans = solve(query,map);
        return ans;
    }
    void setMap(Map<String, List<Integer>> map,String[] info){
        for(String inf:info){
            StringTokenizer stk=new StringTokenizer(inf);
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<4;i++) sb.append(stk.nextToken());
            int score=Integer.parseInt(stk.nextToken());
            // push to map
            if(!map.containsKey(sb.toString())){
                List<Integer> arr=new ArrayList<>();
                arr.add(score);
                map.put(sb.toString(),arr);
            }
            else{
                List<Integer> arr = map.get(sb.toString());
                arr.add(score);
            }
        }
    }
    void sortMap(Map<String, List<Integer>> map){
        for(List<Integer> arr:map.values()){
            Collections.sort(arr);
        }
    }
    int[] solve(String[] query, Map<String, List<Integer>> map){
        List<String> listA=new ArrayList<>();
        List<String> listB=new ArrayList<>();
        List<String> listC=new ArrayList<>();
        List<String> listD=new ArrayList<>();
        int[] ret=new int[query.length];
        int score;
        int idx=0;
        for(String str:query){
            String[] strList=str.split(" and | ");

            listA.clear();
            String queryA=strList[0];
            if(queryA.equals("-")) {listA.add("cpp");listA.add("java");listA.add("python");}
            else listA.add(queryA);

            listB.clear();
            String queryB=strList[1];
            if(queryB.equals("-")) {listB.add("backend");listB.add("frontend");}
            else listB.add(queryB);

            listC.clear();
            String queryC=strList[2];
            if(queryC.equals("-")) {listC.add("junior");listC.add("senior");}
            else listC.add(queryC);

            listD.clear();
            String queryD=strList[3];
            if(queryD.equals("-")) {listD.add("chicken");listD.add("pizza");}
            else listD.add(queryD);

            score=Integer.parseInt(strList[4]);

            int tmp=0;
            for(String strA:listA){
                for(String strB:listB){
                    for(String strC:listC){
                        for(String strD:listD){
                            StringBuilder sb=new StringBuilder();
                            sb.append(strA);sb.append(strB);
                            sb.append(strC);sb.append(strD);
                            // 이진탐색으로 tmp 에 더함
                            tmp+=getLowerBound(sb.toString(),score,map);
                        }
                    }
                }
            }
            ret[idx++]=tmp;
        }
        return ret;
    }
    int getLowerBound(String query,int score,Map<String, List<Integer>> map){
        // map 에서 score list 받기
        List<Integer> scoreList;
        if(!map.containsKey(query)) return 0;
        scoreList=map.get(query);

        // scoreList 가 있다면 로어 바운드로 score 이상값중 낮은 인덱스 찾기
        int s=0,e=scoreList.size()-1;
        int lbound=-1;
        int ret=0;
        while(s<=e){
            int mid=(s+e)/2;
            if(scoreList.get(mid)>=score) {e=mid-1;lbound=mid;}
            else s=mid+1;
        }
        if(lbound==-1) return 0;
        else return (scoreList.size()-lbound);
    }
}