순위 검색

처음에는 HashMap 을 여러개 사용해서 하려고 했으나 "-" 때문에 포기..
찾아보고 이해하고 다시 풀어보았다. 그렇나 디버깅 한세월 걸렸다 하...

https://school.programmers.co.kr/learn/courses/30/lessons/72412

지원자의 4가지 항목을 가지고 16가지의 조합을 만들어서 키로 사용하고
키마다 해당 지원자가 몇명이 있는지 사용해서 푸는 방식이다

import java.util.*;

class Solution {
    public int[] solution(String[] info, String[] query) {
        
        
        HashMap<String, List<Integer>> map = new HashMap<>();
        
        for(String cand : info)
        {
            
            String[] input = cand.split(" ");
            int score = Integer.parseInt(input[4]);
            for(int i = 0; i < 16; ++i)
            {
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < 4; ++j)
                {
                    if((i & (1<<j))>0)
                    {
                        sb.append(input[j]);
                    }
                }
                
                //System.out.println(sb.toString());
                
                if(map.containsKey(sb.toString()))
                {
                    map.get(sb.toString()).add(score);    
                }
                else
                {
                    List<Integer> list = new ArrayList();
                    list.add(score);
                    map.put(sb.toString(), list);
                    
                }
            }
        }
        
        Set<String> keys = map.keySet();
        for(String key : keys)
        {
            if(map.containsKey(key))
            {
                List<Integer> list = map.get(key);   
                Collections.sort(list);
            }      
        }    
        
        ArrayList<Integer> arrAnswer = new ArrayList<>();
        for(String quri : query)
        {
            StringBuilder sb = new StringBuilder();
            String[] input = quri.split(" and | ");
            int score = Integer.parseInt(input[4]);
            
            sb.append(input[0]);
            sb.append(input[1]);
            sb.append(input[2]);
            sb.append(input[3]);
            
            String key = sb.toString().replaceAll("-","");
            //System.out.println(key);
            
            if(map.containsKey(key)==false)
            {
                arrAnswer.add(0);
                continue;
            }
                      
            List<Integer> list = map.get(key);
            
            int count = 0;
            int start = 0;
            int end = list.size()-1;
            int mid = 0;
            //System.out.println(list.size());
            
            while(start <= end)
            {
                mid = (start+end)/2;
                if(list.get(mid) < score)
                {
                    start = mid+1;
                }
                else{
                    end = mid-1;
                }
                    
                
                //System.out.println(start + "," + mid + "," + end);
            }
                       
            arrAnswer.add(list.size() - start);
        }
        
        int[] answer = new int[arrAnswer.size()];
        for (int i = 0; i < arrAnswer.size(); i++) {
            answer[i] = arrAnswer.get(i);
        }

        return answer;
    }
}