[알고리즘 TIL] 순위 검색

문제

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

프로그래머스

 

설명

쿼리문에 들어맞는 지원자 수가 몇인지 알아내는 문제이다. 처음에는 완전 탐색으로 풀었더니, 정확성은 다 맞았지만 효율성에서 다 틀렸다..

class Solution {
    public int[] solution(String[] info, String[] query) {
            int[] answer = new int[query.length];

            //데이터 초기화
            String[][] volunteers = new String[info.length][5];
            String[][] inquiries = new String[query.length][5];

            for (int i = 0; i < info.length; i++) {
                String[] infoArray = info[i].split(" ");
                for (int j = 0; j < 5; j++) {
                    volunteers[i][j] = infoArray[j];
                }
            }

            for (int i = 0; i < query.length; i++) {
                String[] queryArray = query[i].split(" and ");
                for (int j = 0; j < 4; j++) {
                    if (j == 3) {
                        String[] lastQuery = queryArray[j].split(" ");
                        String soulFood = lastQuery[0];
                        String score = lastQuery[1];

                        inquiries[i][3] = soulFood;
                        inquiries[i][4] = score;
                    } else inquiries[i][j] = queryArray[j];
                }
            }

            //각 쿼리마다 해당하는 지원자 수 탐색
            for (int i = 0; i < query.length; i++) {
                int count = 0;
                for (int j = 0; j < info.length; j++) {
                    for (int k = 0; k < 5; k++) {
                        if (k==4) {
                            int queryScore = Integer.parseInt(inquiries[i][k]);
                            int volunteerScore = Integer.parseInt(volunteers[j][k]);
                            if (volunteerScore >= queryScore) count++;
                        } else if (!(inquiries[i][k].equals("-"))&& !(inquiries[i][k].equals(volunteers[j][k]))) break;
                    }
                }
                answer[i] = count;
            }

            return answer;
        }
}

즉, query와 info를 하나씩 비교하면 시간 초과가 난다.

=> 50,000(info) * 100,000(query) * 5 = 25,000,000,000 (약 250초.. 시간 복잡도 최악)

 

이진 탐색을 활용하여 문제를 풀어보자.

info의 언어, 직군, 경력, 소울푸드 조합이 속할 수 있는 모든 경우의 수와 점수를 각각 key와 value로 하는 map에 넣어준다.

ex) ["java", "backend", "junior", "pizza", "150"]는 아래의 모든 경우에 해당되므로, 점수를 넣어준다.

info에 대해 처리를 완료하면, 다음과 같다.

map의 value인 점수 List를 오름차순 정렬 후, query의 조합으로 map을 조회하여 해당하는 값들을 이분 탐색하여 query의 score 이상 받은 사람 수를 구한다.

=> 100,000(query) * log 50,000(info) = 1,500,000 (약 0.1초)

 

이분 탐색이라는 알고리즘을 알고 있었지만, 이를 해당 문제에 적용하기에는 많이 어려웠다. 완전 탐색이 효율성이 좋지 않다면, 이진 탐색을 고려해보도록 하자.

구현

class Solution {
    static HashMap<String, List<Integer>> map;
 
    public static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        map = new HashMap<String, List<Integer>>();
 
        for (int i = 0; i < info.length; i++) {
            String[] p = info[i].split(" ");
            makeSentence(p, "", 0);
        }
 
        for (String key : map.keySet())
            Collections.sort(map.get(key));
 
        for (int i = 0; i < query.length; i++) {
            query[i] = query[i].replaceAll(" and ", "");
            String[] q = query[i].split(" ");
            answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
        }
 
        return answer;
    }
 
    // 이분 탐색
    private static int binarySearch(String key, int score) {
        List<Integer> list = map.get(key);
        int start = 0, 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;
    }
 
    // info가 포함될 수 있는 문장
    private static void makeSentence(String[] p, String str, int cnt) {
        if (cnt == 4) {
            if (!map.containsKey(str)) {
                List<Integer> list = new ArrayList<Integer>();
                map.put(str, list);
            }
            map.get(str).add(Integer.parseInt(p[4]));
            return;
        }
        makeSentence(p, str + "-", cnt + 1);
        makeSentence(p, str + p[cnt], cnt + 1);
    }
}