Programmers - 순위 검색 with JAVA (V)

 

 

 

 

로직

1. Map을 만든다.

예시 : java, backend, senior, pizza -> javabackendseniorpizza,  javabackendsenior-,  javabackend--,  java--- 등

시간 복잡도 : 50000 * 16 = 80만

(+) HashMap<String, List<Integer>> 만들때, 시간 복잡도를 낮추기 위해 아래와 같이 작성한다.

기존에는 map.get(value)를 하나하나 불러와 입력해서 시간복잡도가 늘어남.

for(String value : new_values){
    if(map.get(value) == null){
        List<Integer> nowList = new ArrayList<>();
        nowList.add(score);
        map.put(value, nowList);
        continue;
    }
    map.get(value).add(score);
}

 

 

2. 각 키마다 리스트 정렬

- 매번 정렬보다 한번에 정렬해 처리하는 방식이 좀더 효율적

- 시간복잡도 : 50000*log50000 = 약 20만

 

 

3. 키마다 이진탐색해서 결과찾기

- 매번 해당 기준보다 높은 수를 찾기보다 이진탐색으로 개수를 찾자

- 시간복잡도 : log50000 = 약 5회

 

bisect_left 자바 구현

// bisect 정리
public static int binary_search(List<Integer> list, int score){
    int start = 0;
    int end = list.size()-1;
    while(start <= end){
        int mid = (start + end) / 2;
        if(list.get(mid) < score){
            start = mid+1;
        }
        else{
            end = mid-1;
        }
    }
    return list.size() - start;
}

 

총 시간 복잡도 : 연산수 약 100만

 

 

전체 코드

import java.util.*;
class Solution {    
    public List<Integer> solution(String[] info, String[] query) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, List<Integer>> map = new HashMap<>();
        for(String now : info){
            String[] sep_now = now.split(" ");
            int score = Integer.valueOf(sep_now[4]);
            List<String> values = new ArrayList<>();
            values.add(sep_now[0]);
            values.add("-");
            List<String> new_values = new ArrayList<>();
            for(String value : values){
                new_values.add(value + sep_now[1]);
                new_values.add(value + "-");
            }
            values = new ArrayList<>();
            for(String value : new_values){
                values.add(value + sep_now[2]);
                values.add(value + "-");
            }
            new_values = new ArrayList<>();
            for(String value : values){
                new_values.add(value + sep_now[3]);
                new_values.add(value + "-");
            }
            // 시간복잡도 낮추기 1
            for(String value : new_values){
                if(map.get(value) == null){
                    List<Integer> nowList = new ArrayList<>();
                    nowList.add(score);
                    map.put(value, nowList);
                    continue;
                }
                map.get(value).add(score);
            }
        }
        // 시간복잡도 낮추기 2
        for(String key : map.keySet()){
            Collections.sort(map.get(key));
        }
        for(String now : query){
            String[] sep_now = now.split(" ");
            StringBuilder sb = new StringBuilder();
            sb.append(sep_now[0]);
            sb.append(sep_now[2]);
            sb.append(sep_now[4]);
            sb.append(sep_now[6]);
            int score = Integer.valueOf(sep_now[7]);
            List<Integer> list = map.get(sb.toString());
            if(list == null){
                answer.add(0);
                continue;
            }
            int count = 0;
            count += binary_search(list, score);
            answer.add(count);
        }
        return answer;
    }
    // bisect 정리
    public static int binary_search(List<Integer> list, int score){
        int start = 0;
        int end = list.size()-1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(list.get(mid) < score){
                start = mid+1;
            }
            else{
                end = mid-1;
            }
        }
        return list.size() - start;
    }
}