순위 검색

import java.util.*;
class Solution {
    private static Map<String, ArrayList<Integer>> allInfo = new HashMap<String, ArrayList<Integer>>();
    private static ArrayList<Integer> score = new ArrayList<Integer>();
 
    public static void DFS(String pos, int depth, String[] info) {
        if (depth == 4) {
            if (!allInfo.containsKey(pos)) {
                score = new ArrayList<>();
                score.add(Integer.parseInt(info[4]));
                allInfo.put(pos, score);
            } else {
                allInfo.get(pos).add(Integer.parseInt(info[4]));
            }
            return;
        }
 
        DFS(pos + "-", depth + 1, info);
        DFS(pos + info[depth], depth + 1, info);
    }
 
    public static int getCount(String key, int score) {
        // 조건에 맞는 것이 없을 때
        if (!allInfo.containsKey(key))
            return 0;
        ArrayList<Integer> scores = allInfo.get(key);
        int mid;
        int left = 0;
        int right = scores.size() - 1;
 
        while (left <= right) {
            mid = (left + right) / 2;
 
            if (scores.get(mid) < score) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return scores.size() - left;
    }
 
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
 
        // 모든 조합에 대한 점수 저장
        for (int i = 0; i < info.length; i++) {
            DFS("", 0, info[i].split(" "));
        }
 
        // 점수 리스트 오름차순 정렬
        for (String key : allInfo.keySet()) {
            ArrayList<Integer> getScores = allInfo.get(key);
            Collections.sort(getScores);
        }
 
        // 이진 탐색
        for (int i = 0; i < query.length; i++) {
            String[] condition = query[i].replaceAll(" and ", "").split(" ");
            answer[i] = getCount(condition[0], Integer.parseInt(condition[1]));
        }
        return answer;
    }
}

 

효율성이 가장 큰 문제였다.

해결 방법은 다음과 같다.

1. '-' 처리를 위해 info에 대한 모든 경우의 조합을 HashMap에 저장한다. 이 때 value는 ArrayList로 설정하여 다른 info의 score도 함께 저장할 수 있도록 한다.

2. ArrayList socre를 오름차순 정렬한다.

3. 이진 탐색을 통해 해당 조건에 맞는 첫 번째 인덱스를  찾아낸 후, 전체 크기에서 해당 인덱스를 뺀 값을 저장한다.

 

정확도는 100%지만 효율성에서 실패한 코드는 아래와 같다.

class Solution {
    public static int Check(String[] condition, String[] candidate) {
 
        int k = condition.length - 1;
        if (!condition[k].equals("-") && Integer.parseInt(condition[k]) > Integer.parseInt(candidate[k])) {
            return 0;
        }
        for (k = 0; k < condition.length - 1; k++) {
            if (!condition[k].equals("-") && !condition[k].equals(candidate[k])) {
                return 0;
            }
        }
 
        return 1;
    }
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        int i, j;
        for (i = 0; i < query.length; i++) {
            String[] condition = new String[5];
            int idx = 0;
            // query 값 받아오기
            for (String q : query[i].split(" ")) {
                if (!q.equals("and"))
                    condition[idx++] = q;
            }
 
            for (j = 0; j < info.length; j++) {
                // info 값 받아오기
                String[] candidate = info[j].split(" ");
                // 조건 비교
                answer[i] += Check(condition, candidate);
            }
        }
        return answer;
    }
}

조건을 하나하나 순차적으로 비교하였다.

이 경우 info * query 만큼의 연산이 필요하게 된다.

 

참고 사이트 : https://loosie.tistory.com/265