[프로그래머스][JAVA] 순위 검색 (인덱싱, 이진 탐색, 비트마스크)

참고 : https://www.youtube.com/watch?v=eBQtFteduyw&t=572s 

 

인덱싱 + 이진 탐색에 대한 이해가 조금 필요한 문제임

인덱싱은 참고 유튜브 보면서 이해했고

( - 하이픈이 해당 정보에 무엇이 와도 상관이 없음인데 이것도 인덱스에 추가해서 정보를 받을 때,

 

ex) "java backend junior pizza 150"

위의 신입 사원 정보를 받을 때 

"java backend junior pizza 150"

"java backend junior - 150"

"java backend - pizza 150"

"java backend - - 150"

"java - junior pizza 150"

"java - junior - 150"

"java - - pizza 150"

"java - - - 150"

"- backend junior pizza 150"

"- backend junior - 150"

...

 

" - - - - 150" 

 

이런 식으로 개발언어/직군/경력/소울푸드가

(  java 또는 - /  backend 또는 -  / junior 또는 -  / pizza 또는 - ) 

이렇게 해서 2^4(16)번 넣어줌

 

로 모든 경우의 수에 전부 score 150점 넣어줘서 나중에 query문을 받을 때

쓸데 없이 탐색하지 않게 해주는 방식이 너무나도 놀라웠다

 

이진 탐색은 Line:66~75인데

원하는 score가 없는 경우 음수가 나오는데 이걸 처리해주면 되고

원하는 score가 있기는 한데 이것이 중복된 값들 중 (중복된 값이 있다고 가정할 때)

어느 위치에 있는지 모르기 때문에 중복된 값들 중 가장 왼쪽의 인덱스를 찾아야 한다

찾고 List.size() - index해주면 score이상의 값이 나오게됨

 

 

import java.util.*;
 
class Solution {
    private static List<List<Integer>> scoreList;
    private static Map<String, Integer> wordMap;
    
    public int[] solution(String[] infos, String[] querys) {
        // List<Integer> list = 
        //   Arrays.asList(new Integer[]{1,3,5,6,6,6,6,6,6,6,8,10});
        // int ret = Collections.binarySearch(list,6);
        // ret = (ret>=0)? ret : -(ret+1);
        // System.out.println(ret);
        
        scoreList = new ArrayList<>();
        wordMap = new HashMap<>();
        initWordMap();
        for(int i=0; i<4*3*3*3; i++){
            scoreList.add(new ArrayList<>());
        }
        
        
        for(String info : infos){
            String[] word = info.split(" ");
            int score = Integer.parseInt(word[4]);
            int[] smallIndex = {
                wordMap.get(word[0])*3*3*3, // 개발언어
                wordMap.get(word[1])*3*3, // 직군
                wordMap.get(word[2])*3, // 경력
                wordMap.get(word[3])  // 소울푸드
            };
           
            for(int i=0; i<(1<<4); i++){
                int index = 0;
                for(int j=0; j<4; j++){
                    if( (i&(1<<j)) !=0){
                        index += smallIndex[j];
                    }
                }
                scoreList.get(index).add(score);
            }
            
        }
        
        for(int i=0; i<4*3*3*3; i++){
            Collections.sort(scoreList.get(i));
        }
        
        
        int[] answer = new int[querys.length];
        for(int i=0; i<querys.length; i++){
            String[] word = querys[i].split(" ");
            int score = Integer.parseInt(word[7]);
            int index = 
                wordMap.get(word[0])*3*3*3+ // 개발언어
                wordMap.get(word[2])*3*3+ // 직군
                wordMap.get(word[4])*3+ // 경력
                wordMap.get(word[6]);  // 소울푸드
            
            // System.out.println("index "+index);
            // scoreList.get(index).forEach(s->{
            //     System.out.print(s+" ");
            // });
            // System.out.println();
            // System.out.println();    
            List<Integer> currList = scoreList.get(index);
            int findedIndex = Collections.binarySearch(currList, score);
            if(findedIndex<0){
                findedIndex = -(findedIndex+1);
            }
            else{
                while(0<=findedIndex-1 
                      && currList.get(findedIndex-1)==score){
                    findedIndex--;
                }
            }
            
            answer[i] = currList.size()-findedIndex;
        }
        
        // for(int i=0; i<scoreList.size(); i++){
        //     System.out.println(i);
        //     scoreList.get(i).forEach(score -> {
        //         System.out.print(score+" ");
        //     });
        //     System.out.println();
        // }
        
        
        
        
        
    
        
        return answer;
    }
    
    private void initWordMap(){
        wordMap.put("-",0);
        wordMap.put("cpp",1);
        wordMap.put("java",2);
        wordMap.put("python",3);
        wordMap.put("backend",1);
        wordMap.put("frontend",2);
        wordMap.put("junior",1);
        wordMap.put("senior",2);
        wordMap.put("chicken",1);
        wordMap.put("pizza",2); 
    }
}