[프로그래머스_카카오]순위검색
풀이 생각
-
완전탐색 → 불가능. 50000 x 100000 → 500억이다
-
따라서 든 생각 1. Hash or Matrix(다차원 배열 형태) 2. 이진탐색(lower bound)
-
문제를 보고 위의 생각은 바로들었는데 Hash로 삽질 했다. 다른 분들은 Hash로 잘 푸시던데 나는 머리에 혼란이 오고 삽질을 몇시간이나 하게되어 큰 스트레스가 된 덕분에 Matrix로 풀이를 바꿔보았다. (애매하게 안 풀리는게 여전히 큰 스트레스고 극복하지 못해 큰일이다...)
- 조건 별로 Map을 생성한다면? 언어Map, 직군Map (X)
==> and로 다른 조건과 함께 하는 것을 못 찾는다. (X)
- 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에 대해서도 같은 것을 반복하였다.
- 카카오 메뉴얼 문제처럼 이것도 아예 조합을 먼저 다 만들어 놓아볼까???
- 점수 빼고, 조건만 조합한다면? "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)
