[프로그래머스 Level2] 순위 검색(JAVA) - 2021 카카오

[문제]

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

코딩테스트 연습 - 순위 검색

 

문제가 길어서 생략하도록 하겠습니다.

 

---

[문제 풀기 전]

처음에는 효율성 처리를 할 방법이 도저히 생각이 나지 않아 정확성이라도 맞추자 하는 심정으로 문제를 풀었습니다. 정확성으로 푼 방법은 쿼리의 개수만큼 반복하는데 쿼리를 split 하여 info에서 찾도록 아주 무식한 방법으로 풀었습니다. 역시 효율성은 당연히 떨어졌습니다. 그래서 답을 좀 이곳저곳 찾아봤는데 기본기가 정말 탄탄해야 풀 수 있도록 설계가 된 문제였습니다.

 

---

[문제 풀이]

 

우선 info가 만들 수 있는 모든 경우를 HashMap 으로 만들어야 합니다. 왜 해시맵인가 하면 해시 특성상 key가 주어지면 O(1)의 속도로 찾을 수 있기 때문에, query에 따라 모든 정보를 하나하나 찾지 않아도 됩니다. 만약 효율성이 틀렸으면 이렇게 query에 따라 info를 하나하나씩 다 찾게 했을 텐데 info와 query의 크기가 5만 , 10만 크기라서  아주 큰 시간 복잡도를 가져 시간 초과가 날 수밖에 없습니다.

그래서 해시맵은 한번 만들 때, 만들고 나서 해시 맵을 바꿀 일이 없게 완벽하게 구현을 해야합니다. 만약 쿼리를 할 때마다 뭔가 연산이 추가가 된다면 검색을 할 때마다 느려진다는 것을 의미합니다.

 

해시맵은 <String, ArrayList<Integer>>의 형태로 만들어지게 됩니다.  예를 들어 문제 기준으로 ----이라는 키가 만들어지면 해당 키는 전체를 의미하기 때문에 150,260,150,210,80,50이라는 값이 들어가게 되어 List의 형태로 관리를 해줘야 합니다. 그리고 만들어진 List는 정렬을 해줘야 합니다. 만약 정렬을 하지 않으면 특정 값 이상의 개수를 찾으려면 for문으로 하나하나 찾아가는게 최악의 경우가 이 또한 5만 * 10만 이 되겠죠. 정렬이 되었으니 이분탐색을 통하여 찾고자 하는 값 보다 큰 값이 처음 나오는 경우를 찾아 해당 전체 크기에서 해당 위치를 빼게 되면 원하는 값을 얻을 수 있습니다. 

 

이 내용을 기반으로 그대로 코드를 구현하면 원하는 답을 얻을 수 있습니다.

 

---

[소스 코드]

 

import java.util.*;

class Solution {

    static HashMap<String, ArrayList<Integer>> hashMap = new HashMap<>();
    static ArrayList<Integer> score = new ArrayList<>();

    public int[] solution(String[] info, String[] query) {
        int[] answer = {};

        //모든 경우의 해시맵 만들기
        for (String i : info) {
            dfs(0, "", i.split(" "));
        }

        //해시맵의 리스트들을 정렬
        for (ArrayList<Integer> list : hashMap.values()) {
            Collections.sort(list);
        }

        answer = new int[query.length];
        int i = 0; //쿼리반복횟수 및 answer[i] 
        for (String q : query) {
            String[] data = q.split(" and ");

            String[] s = data[3].split(" ");
            int target = Integer.parseInt(s[1]); //찾아야할 값
            data[3] = s[0];

            String key = String.join("", data);

            if (hashMap.containsKey(key)) {
                ArrayList<Integer> list = hashMap.get(key);
                int start = 0;
                int end = list.size() - 1;

                while (start <= end) {
                    int mid = (start + end) / 2;

                    if (list.get(mid) < target) {
                        start = mid + 1;
                    }else{
                        end = mid - 1;
                    }
                }

                answer[i] = list.size() - start;
            }
            i++;
        }
        return answer;
    }

    static void dfs(int depth, String query, String[] info) {
        if(depth == 4){
            if (!hashMap.containsKey(query)) {
                score = new ArrayList<>();
                score.add(Integer.parseInt(info[4]));
                hashMap.put(query, score);
            }else{
                hashMap.get(query).add(Integer.parseInt(info[4]));
            }
            return;
        }

        dfs(depth + 1, query + "-", info);
        dfs(depth + 1, query + info[depth], info);
    }
}