문제
데이터를 주고 쿼리를 처리해보라는 문제다.
단순하게 문자열로 잘라서 갯수를 세어보기만하면 될 줄 알았다.
구현
컬럼수만큼 배열을 만들고 카운트 해주는 식으로 도전했다.
// 간단한 처리를 위해 문자를 각각 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 이라는 데이터가 들어온다면
처음부터 - 칸을 고려한 모든 경우의 수를 먼저 넣어줄지
아니면 나중에 쿼리를 처리할때 여러번 계산해줄지 선택할수있다.
- 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);
}
}