순위 검색

효율성이 존재하는걸 보고 순차탐색은 절대 안될것이라고 생각함.
먼저 info와 query를 어떤방식으로 처리할수있는가?를 물어보는 문제.
다음으로는 -라는 모든 것에 대해서 처리를 할수있는가를 묻는다.
마지막으로 info와 query를 어떤방식으로 처리할지를 물어본다.

1. info는 split을 통해서 자를수있다 이때 모든것에 대해서 처리를 할수 있어야하는데 생각해보면 BFS로 해결할수있는 문제지만 이 경우에는 모든것과 자신 두가지로 구분하기때문에 비트마스크로도 해결이 가능하다. 그러면 종류가 4가지인(점수를 제외) 가짓수는 2^4인 16이다. 이것을 통해서 비트마스크로 해결하는 방식을 선택했다.

2. map에는 computeIfAbsent라는 함수가 존재한다 키가 존재하지 않으면 다음의 람다식이나 함수를 실행시키는 모습이고 리턴이 존재한다면 자기자신이다.

3. info를 넣어놓을 map과 query를 순회할수있는 내용이 만들어졌다면 쿼리를 돌렸을때 map안에서 있는 값을 탐색할수있는 방법을 찾아야한다. value의 값으로 이분탐색을 한다면 O(n)가 아닌 O(logn)로 접근이 가능하다. 따라서 순차탐색보다는 이분탐색을 통해서 값을 찾아내기 위해서 먼저 정렬이 필요하다.

4. 정렬이 완성이 된다면 순차탐색을 돌려서 값을 찾아 리턴하면 끝나는 문제.

코드

import java.util.*;
class Solution {
   public int[] solution(String[] info, String[] query) {
       HashMap<String,ArrayList<Integer>> infoMap = new HashMap<>();
       int tokenLength = info[0].split(" ").length-1;
       int[] answer = new int[query.length];
       int count=0;
       //info 자르기
       for(String name : info){
           String[] token = name.split(" ");
           int value = Integer.parseInt(token[4]);
           //비트마스크
           for(int i=0;i<(1<<tokenLength);i++){
               StringBuilder sb = new StringBuilder();
               //-는 무시한다 언어 직군 경력 소울푸드 4가지기 때문에 j<4
               for(int j=0;j<4;j++){
                   if((i & (1<<j))>0){
                       sb.append(token[j]);
                   }
               }
               //computeIfAbsent의 리턴값은 자기자신
               infoMap.computeIfAbsent(sb.toString(), (s)-> new ArrayList<Integer>()).add(value);
           }
       }    
       //만들어진 hashmap의 arraylist정렬
       for(String key : infoMap.keySet()){
           Collections.sort(infoMap.get(key));
       }
      
  //전체 출력 info완성
//        for(String key : infoMap.keySet()){

//             List<Integer> value = infoMap.get(key);

//             System.out.println(key+" : "+value);

//         }
       //query 순회
       for(String qu:query){
           String tmp = qu.replaceAll("-","").replaceAll(" and ","");
           String[] list = tmp.split(" ");
          
           //이분탐색 함수
           if(infoMap.containsKey(list[0]))
               answer[count++]=binarySearch(infoMap.get(list[0]),Integer.parseInt(list[1]));
           else
               answer[count++]=0;
       }
       
       return answer;
   }
   //이분탐색
   int binarySearch(ArrayList<Integer> list,int value){
       int start =0,end= list.size()-1;
       int mid;
       while(start<=end){
           mid = (start + end)/2;
           if(list.get(mid)>=value){
               end = mid -1;
           }else{
               start = mid +1;
           }                   
       }
       
       return list.size()-start;
   }
   
}

문제하나에 많은 요구를 원하는 문제여서 생각하기 쉽지않았다.