프로그래머스 순위 검색 [level2][2021][카카오]

문제를 풀 때 참고한 분의 블로그 

https://loosie.tistory.com/265

[프로그래머스] 2021 카카오 / 순위 검색 (Java)

---

해당 문제는 Level3은 되지 않을까 하는... 넓은 알고리즘 역량이 필요한 문제이다.

 

1. 조합을 다룰 수 있어야 한다.

 

2. 이분 탐색을 그 자리에서 구현할 수 있어야 한다.

 

3. Map 자료구조와 List 자료구조를 능숙하게 다룰 수 있어야 한다.

 

---

첫 번째 접근.

 

20분 정도 문제를 읽으면서 고민했을 때 주어진 경우의 수가 많지 않기에 객체로 두어서 Map으로 처리하면 편하게 진행할 수 있을 것 같다는 생각이 들었다.

 

Applicant 객체를 두고 language, job, career, soulfood 변수를 가지고 해당 변수들에 대한 Equals() 메서드와 HashCode()를 오버라이드 해주면 Map에서 해당 객체에 대한 key를 생성할 수 있다.

 

문제는 '-' 를 고려해야 한다는 것이다. -가 개입된 순간 경우의 수가 엄청나게 복잡하게 늘어나버렸다.

 

-의 경우 들어갈수도 있고 들어가지 않을 수도 있고 한 곳에만 존재하는 것도 아니다..

 

=> -을 위한 조합을 생각해야 했다.

 

그 자리에서 dfs를 구현했다. depth = 0으로 두고 n개 중에서 n개를 뽑는 경우의 수를 체크했다.

Key에 depth 별로 -을 뽑고 안 뽑고로 진행했다. => 1개의 info당 16개의 경우의 수가 나온다.

 

void dfs(String pos, int depth, String[] info) {

        if(depth == 4) {
            if(!allInfo.containsKey(pos)) {
                in = new ArrayList<>();
                in.add(Integer.parseInt(info[4]));
                allInfo.put(pos, in);
            }else {
                allInfo.get(pos).add(Integer.parseInt(info[4]));
            }
            return;
        }
        dfs(pos+"-", depth+1, info);
        dfs(pos+info[depth], depth+1, info);

    }

위의 조합이 생성된다.

위의 모든 조합은 주어지는 쿼리에서 score를 확인하게 되는 경우이다.

 

2. 이후에 List들을 추출해서 이분 탐색이 가능하도록 정렬해줘야 한다.

[ 효율성 체크가 따로 있기에 이분 탐색을 가능하게 해줘야 한다. ]

 

        List<String> keyset = new LinkedList<>(map.keySet());
        for(int i = 0; i < keyset.size(); i++) {
            List<Integer> scoreList = map.get(keyset.get(i));
            Collections.sort(scoreList);
        }

 

3. 이후 이분탐색 로직을 두고 query별로 이분 탐색을 실행하게 한다.

        int idx = 0;
        for(String query : querys) {
            String[] splited = query.split(" and ");
            String[] foodandscore = splited[3].split(" ");
            String food = foodandscore[0];
            int score = Integer.parseInt(foodandscore[1]);
            
            String key = splited[0] + splited[1] + splited[2] + food;
            answer[idx++] = search(key, score);
        }
        
            
    int search(String key, int score) {
        if(!map.containsKey(key)) return 0;
        
        List<Integer> scoreList = map.get(key);
        
        int start = 0;
        int end = scoreList.size() - 1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(scoreList.get(mid) < score) start = mid + 1;
            else end = mid - 1;
        }
        
        return scoreList.size() - start;
    }

 

전체 코드

 

import java.util.*;

class Solution {
    
    Map<String, List<Integer>> map = new HashMap<>();
    public int[] solution(String[] infos, String[] querys) {
        int[] answer = new int[querys.length];
        
        // 모든 조합에 대한 key를 가지기
        for(String info : infos) {
            String[] splited = info.split(" ");
            dfs(splited, "", 0, 4, 4);
        }
        
        List<String> keyset = new ArrayList<>(map.keySet());
        for(int i = 0; i < keyset.size(); i++) {
            List<Integer> scoreList = map.get(keyset.get(i));
            Collections.sort(scoreList);
        }
        
        int idx = 0;
        for(String query : querys) {
            String[] splited = query.split(" and ");
            String[] foodandscore = splited[3].split(" ");
            String food = foodandscore[0];
            int score = Integer.parseInt(foodandscore[1]);
            
            String key = splited[0] + splited[1] + splited[2] + food;
            answer[idx++] = search(key, score);
        }
        return answer;
    }
    
    int search(String key, int score) {
        if(!map.containsKey(key)) return 0;
        
        List<Integer> scoreList = map.get(key);
        
        int start = 0;
        int end = scoreList.size() - 1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(scoreList.get(mid) < score) start = mid + 1;
            else end = mid - 1;
        }
        
        return scoreList.size() - start;
    }
    
    void dfs(String[] s, String output, int d, int n, int r) {
        if(d == r) {
            System.out.println(output);
            //logic
            List<Integer> list;
            int score = Integer.parseInt(s[4]);
            if(map.containsKey(output)) {
                list = map.get(output);
                list.add(score);
                map.put(output, list);
            } else {
                list = new ArrayList<>();
                list.add(score);
                map.put(output, list);
            }
        } 
        if(d == n) return ;
        
        dfs(s, output + s[d], d + 1, n, r);
        dfs(s, output + "-", d + 1, n , r);
    }
}

어려웠던 문제....

 

해당 문제에서 LinkedList<>()로 score를 담으면 sort()의 효율성이 뒤쳐져서 효율성 테스트를 통과하지 못한다.

ArrayList<>()의 경우 배열로 전환하고 정렬을 처리하기 때문에 더 효율적인 시간을 얻게 된다. [ 살짝 더 효율적이라고 한다. ]

이에 대해서 다음의 글이 잘 분석해주었다.

https://coderstower.com/2019/08/06/arraylist-vs-linkedlist-sort-get-iteration/

ArrayList vs LinkedList: Sort, Get and Iteration

 

마무리...

 

순열 + 조합에 대하여 문제에서 해결해야 하는 로직을 처리해야 하는 문제는 많이 만났는데 이런 유형의 문제는 효율성을 따로 묻지는 않았었다.

 

오늘 만난 문제는 효율성을 물어봄으로써 전체 로직에서 효율적으로 처리해야 하는 부분을 고민하게끔 만들어주었다.

 

그 과정에서 구현해야 했던게 이분 탐색이지 않을까 한다.

 

개인적으로 Level3에 가까운 문제라고 생각된다.

 

해당 문제를 풀 수 있다면 완전탐색을 푸는 역량이 상당히 높아졌다고 봐도 무방할 듯 하다.