[프로그래머스] Lv.2 순위 검색

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

프로그래머스

 

문제 접근 방법

1. 문제에서 주어진 Info 정보를 기반으로 해쉬맵을 생성한다.

2. 각 해쉬맵의 value를 오름차순으로 정렬한다.

3. query 조건에 맞는 지원자를 가져온다.

4. 이분 탐색을 통해서 lower bound를 찾는다.

 

import java.util.*;
class Solution {
    static Map<String, ArrayList<Integer>> map = new HashMap<>();
    public int[] solution(String[] info, String[] query) {
        
        for(String s : info) {
            String [] str = s.split(" ");
            String [] languages = {str[0], "-"};
            String [] jobs = {str[1], "-"};
            String [] exps = {str[2], "-"};
            String [] foods = {str[3], "-"};
            int score = Integer.parseInt(str[4]);
            // 4 * 3 * 3 * 3 = 108
            for (String language : languages)
                for(String job : jobs)
                    for(String exp : exps)
                        for(String food : foods) {
                            String [] keys = {language, job, exp, food};
                            String key = String.join(" ", keys);
                            ArrayList<Integer> arr = map.getOrDefault(key, new ArrayList<>());
                            arr.add(score);
                            map.put(key, arr);
                            
                        }
        }
        // 오름차순
        for(ArrayList<Integer> arr : map.values()) {
            Collections.sort(arr);
        }
        
        map.forEach((key,value) -> System.out.println(key + " : " + value));
        
        // 쿼리 조건에 맞는 지원자를 가져온다.
        int [] answer = new int[query.length];
        int idx = 0;
        for(String q : query) {
            String [] str = q.split(" and ");
            int target = Integer.parseInt(str[3].split(" ")[1]);
            str[3] = str[3].split(" ")[0]; // 숫자를 제외한 값들만 key로 가지기 위해
            String key = String.join(" ", str);
            
            if (map.containsKey(key)) {
                ArrayList<Integer> list = map.get(key);
                int start = 0;
                int end = list.size();
                while (start < end) {
                    int mid = (start + end) / 2;
                    if (list.get(mid) >= target) {
                        end = mid;
                    }
                    else start = mid + 1;
                }
                answer[idx] = list.size() - start;
            }
            idx++;
        }
        return answer;
    }
}

 

문제 풀이 회고

 

카카오 문제는 레벨 + 1씩 해야할 것 같다...

 

힌트를 봤음에도 이해가 되지 않는 것이 두가지 였다.

1. 해쉬맵에 왜 모든 경우의 수를 key에 저장하는가?
2. 왜 점수를 ArrayList 형태로 저장하는가?

 

1번 같은 경우는 "-"에 대한 케이스를 고려하지 못해서 헷갈렸다.

 

"- and - and - and - 150"와 같은 조건이 쿼리에 있을 때, 저 "-"에는 아무 값이나 들어와도 상관없고 단지 점수만 150점을 넘으면 된다는 소리다. 그렇기 때문에 모든 경우의 수에 대해서 해쉬맵에 key 형태로 저장을 해줘야 한다.

 

2번은 

- - - - 이런식으로 입력값이 주어진다면 모든 지원자들을 의미하는 것이기 때문에 모든 숫자 정보를 포함해야 한다.

[50, 80, 150, 150, 210, 260] 

그러므로, 단순히 Integer로 저장하는 것이 아닌 ArrayList로 저장해줘야 한다!

 

 

 

 

 

https://www.youtube.com/watch?v=vFwVvJQnC4M