[Java] 프로그래머스 : 순위 검색

1. 문제

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

프로그래머스

 

2. 풀이 과정

처음엔 시간 계산안하고 풀어서 효율성에서 딱걸렸다.

(info의 크기) x (query의 크기)는 50억으로 2중 반복문 도는 순간 무조건 효율성에서 걸린다.

따라서 메모리를 좀 더 쓰더라도 (info의 크기) + (query의 크기)가 되도록 해야한다.

구체적인 프로세스는 아래와 같다.

1) info를 돌면서, 모든 가능한 경우를 Key값으로, 점수를 Value로 한다. 즉, Map<String, List<Integer>>에 파싱해서 넣어주면 된다. 이렇게 경우의 수를 구하는 건 2^4이므로 얼마 걸리지 않는다.

     ex) 'java backend junior pizza'에 대한 key값 예시 : javabackendjuniorpizza, -backendjuniorpizza, ... , ---- 

2) Map에 있는 모든 배열을 정렬해준다. 전체 경우의 수(info크기*2^4)보다 query의 개수가 훨씬 크기 때문에 미리 정렬하는 것이 이득이다.

3) 이제, 각 query를 키값으로 만들어, 점수 배열을 찾고, 그 점수 배열은 이진 탐색을 통해 조건을 만족하는 데이터의 개수를 찾는다.

 

import java.util.*;

class Solution {
    
    public int[] solution(String[] info, String[] query) {
        
        //1.
        Map<String, List<Integer>> scoreMap = new HashMap<>();
        
        for(int i=0; i<info.length; i++){
            StringTokenizer st = new StringTokenizer(info[i]);
            recur(0, scoreMap, 
                  new String[]{st.nextToken(), st.nextToken(), st.nextToken(), st.nextToken()}, 
                  Integer.parseInt(st.nextToken()));
        }
        
        scoreMap.forEach((k, v) -> Collections.sort(v));
        
        //2.
        int[] answer = new int[query.length];
        for(int i=0; i<query.length; i++){
            String[] conditions = query[i].split(" ");
            String now = conditions[0] + conditions[2] + conditions[4] + conditions[6];
            int score = Integer.parseInt(conditions[7]);
            
            List<Integer> scores = scoreMap.getOrDefault(now, new ArrayList<>());
            
            //
            int pos = binarySearch(scores, score, 0, scores.size()-1);
            if(pos < 0) answer[i] = 0;
            else answer[i] = scores.size() - pos;
                
        }
        
            
        return answer;
        
    }
    
    public int binarySearch(List<Integer> scores, int num, int l, int r){
        while(l <= r){
            int m = (l+r)/2;
            
            if(num <= scores.get(m)){
                r = m-1;
            } else{
                l = m+1;
            }
        }
        
        return l;
    }
    
    public void recur(int index, Map<String, List<Integer>> scoreMap, String[] infos, int score){
        if(index >= 4){
            String key = infos[0]+infos[1]+infos[2]+infos[3];
            List<Integer> scores = scoreMap.getOrDefault(key, new ArrayList<>());
            scores.add(score);
            scoreMap.put(key, scores);
            return;
        }
        
        recur(index+1, scoreMap, infos, score);
        
        String temp = infos[index];
        infos[index] = "-";
        recur(index+1, scoreMap, infos, score);
        infos[index] = temp;
    }
        
}