[프로그래머스] 순위 검색 - java

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

코딩테스트 연습 - 순위 검색

import java.util.*;
class Solution {
	static HashMap<String, List<Integer>> map = new HashMap<>();
	
    public int[] solution(String[] info, String[] query) {
    	int[] answer = new int[query.length];
        for(int i=0; i<info.length; i++) {
        	dfs("", info[i].split(" "), 0);
        }
        
        for(String key :map.keySet()) {
        	Collections.sort(map.get(key));
        }
        
        for(int i=0; i<query.length; i++) {
        	String temp[] = query[i].replace(" and ", "").split(" ");
        	int score = Integer.parseInt(temp[1]);
        	answer[i] = binarySearch(temp[0], score);
        	
        }
        return answer;
    }
    
    private int binarySearch(String string, int score) {
    	if(map.containsKey(string)) {
    		List<Integer> list = map.get(string);
    		int left = 0;
    		int right = list.size()-1;
    		if(list.get(right) < score) {
    			return 0;
    		}
    		
    		while(left<right) {
    			int mid = (left+right)/2;
    			if(list.get(mid) < score) {
    				left = mid+1;
    			}
    			else{
    				right = mid;
    			}
    		}
    		return list.size() - left;
    	}
    	return 0;
	}

	private void dfs(String s, String[] info, int depth) {
    	if(depth == 4) {
    		if(map.containsKey(s) == false) {
    			List<Integer> list = new ArrayList<Integer>();
    			list.add(Integer.parseInt(info[4]));
    			map.put(s, list);
    		}
    		else {
    			map.get(s).add(Integer.parseInt(info[4]));
    		}
    		return;
    	}
    	
    	dfs(s+"-", info, depth+1);
    	dfs(s+info[depth], info, depth+1);
    }
}

선형적으로 풀면 info 배열의 최대 크기는 5만, query 배열의 최대 크기는 10만 이므로 최대 50억 연산을 하게 되므로 효율성을 통과하지 못하므로 이분탐색을 활용해주었습니다.

 

java backend junior pizza 150 의 경우

```

- backend junior pizza

java - junior pizza

java backend - pizza

java backend junior -

- - junior pizza

- backend - pizza

~~~~~

```

처럼 16개로 표현할 수 있다.

dfs를 활용해 해쉬맵에 모든 경우의 수를 <String, List> 형식으로 등록한 후에

쿼리문을 해쉬맵에 참조해 이분탐색을 활용해 풀 수 있습니다.