프로그래머스 - 순위 검색 - 완전탐색+이진탐색 - Java

1. 문제

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

2. 풀이

어떤 것을 이진탐색으로 할지가 가장 고민이 될 수 있다.

해당 문제는 info에서 주어진 문자열들의 모든 조합을 완전탐색으로 구현하여 -> 조합안에 있는 점수들을 이진탐색 하는 것.

문제의 가장 핵심 조건

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

즉 X점 이상 이기 때문에
조합 안의 가능한 점수들이 50, 100, 180, 200 이면
X = 90일때 90점 이상을 받은 사람은 3명인 것이다.

이진탐색에서는
lowerBound : 찾고자 하는 값(이상의)값이 처음으로 나타나는 위치를 사용한다.
참고 - 내 풀이

이 점수들을 어디에다가 저장할 것인가?
info배열을 돌면서 가능한 조합을 보고 -> 그 조합에다가 List<>를 선언하여 점수를 차례대로 저장해준다.

info[0] : "java backend junior pizza 150" 이걸 dfs를 돌면서 -를 넣고, 가능한 모든 조합을 구해 이를 Map에다가 넣는다.

조합을 모두 구한 후 query를 돌면서 수행한다. 이때 "java and backend and junior and pizza 100" 를 먼저 " and "를 ""로 잘라줘야 Map안에 있는 Key들과 매치가 된다. String[] newQ = qStr.split(" "); 이렇게 하면
newQ[0] : javabackendjuniorpizza
newQ[1] : 100

이렇게 들어가게 되어 newQ[0]에 해당하는 List를 Map에서 가져오고, newQ[1]의 값을 target으로 잡아 binarySearch를 수행한다.

3. 전체 코드

import java.util.*;

class Solution {
    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++){
            String[] p = info[i].split(" ");
            makeSentence(p, "", 0);
        }
        
        for(List<Integer> list : map.values()){
            Collections.sort(list);
        }
        
        for(int i = 0; i < query.length; i++){
            String qStr = query[i].replace(" and ", "");
            String[] newQ = qStr.split(" ");
            answer[i] = map.containsKey(newQ[0]) ? binarySearch(newQ[0], Integer.parseInt(newQ[1])) : 0;
        }
        
        return answer;
    }
    
    public int binarySearch(String str, int score){
        List<Integer> list = map.get(str);
        
        int start = 0;
        int end = list.size();
        
        while(start < end){
            int mid = (start + end) / 2;
            
            if(list.get(mid) >= score){
                end = mid;
            } else{
                start = mid + 1;
            }
        }
        
        return list.size() - end;
    }
    
    public void makeSentence(String[] q, String str, int index){
        if(index == q.length - 1){
            if(!map.containsKey(str)){
                map.put(str, new ArrayList<>());
            }
            map.get(str).add(Integer.parseInt(q[q.length - 1]));
            return;
        }
        
        makeSentence(q, str + "-", index + 1);
        makeSentence(q, str + q[index], index + 1);
    }
}