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

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

프로그래머스

이 문제는 이진탐색을  사용하여 풀 수 있다.

 

 

핵심 

이 문제는 정확성만 보자면, 완전탐색으로 구할 수 있다. 하지만 효율성을 통과하기 위해 이진탐색을 사용해야 한다.

info의 정보를 가지고 "-"를 포함한 모든 조합을 map의 키값으로 가지고 이후 value값을 정렬시켜 이진탐색을 하면 된다.

 

 

정답 코드

import java.util.*;
class Solution {
    static Map<String,List<Integer>> map;
    public int[] solution(String[] info, String[] query) {
        map = new HashMap<>();
        for(String i : info){
            String[] arr = i.split(" ");
            comb(arr,0,"");
        }

        for(String k : map.keySet())Collections.sort(map.get(k));


        int[] answer = new int[query.length];
        for(int i = 0; i < query.length; i++){
            String[] q = query[i].replace(" and ","").split(" ");
            int index = 0;
            if(map.containsKey(q[0]))index =binary(map.get(q[0]),Integer.parseInt(q[1]));
            answer[i] = index;
        }
        return answer;
    }

    public int binary(List<Integer> list, int value){
        int start = 0;
        int end = list.size()-1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (list.get(mid) < value)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return list.size() - start;
    }

    public void comb(String[] info, int index, String result){
        if(index == 4){
            if(!map.containsKey(result)){
                List<Integer> list = new ArrayList<>();
                map.put(result,list);
            }
            map.get(result).add(Integer.parseInt(info[4]));
            return;
        }

        comb(info,index+1, result+"-");
        comb(info,index+1,result+info[index]);
    }
}

해설

앞서 말한 대로 info의 정보를 "-"를 포함한 조합을 만들어서 map에 값을 넣는다.

ex) java, backend, junior, pizza, 150으로 배열을 만들면

-> - , backend, junior, pizza, 150 , java, -, junior, pizza, 150, java, backend, -, pizza, 150...

이후 value값을 정렬시킨다. 이진탐색을 사용하기 위함이다.

ex) 100, 150, 200, 250, 300 이면 150 이후는 모두 150 이상이기 때문에 빠르게 원하는 답을 구할 수 있음

만약 키값이 존재한다면 binary를 통해 위치를 찾고, 값을 반환한다.

 

 

 

배운 점

처음에는 완전탐색을 사용하여 풀었다. 효율성에서 실패가 뜬 이후 이진탐색을 통해 풀려하였다.

Collections.binarySearch()를 이용하려 하였는데, 이는 해당값이 존재하지 않으면 -1을 반환한다는 것이

문제를 풀기에 적합하지 않았다. 이유는 100 ,150 ,200 이 있다고 할 때 120점 이상을 찾고 싶어도 120이 없기 때문에

-1을 반환하기 때문이었다. 따라서 binary를 새로 만들어서 값이 없어도 큰 값의 위치를 반환하도록 만들었다.

재미있는 문제였다고 생각한다.