프로그래머스 lv2 순위 검색

문제 링크

순위 검색

풀이

1차 풀이

• 도저히 방법이 생각나지 않아서 무식하게 풀어보았다.

  import java.util.Arrays;
  
   class Solution {
    public static int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
  
        for (int i = 0; i < query.length; i++) {
            int cnt = 0;
            String[] splited = query[i].split(" and ");
            String standardScore =  splited[splited.length - 1].split(" ")[1];
            splited[splited.length - 1] = splited[splited.length - 1].split(" ")[0];
            for (String information : info) {
                String[] split = information.split(" ");
                if (Integer.parseInt(split[split.length - 1]) >= Integer.parseInt(standardScore)) {
                    for (int j = 0; j < split.length - 1; j++) {
                        if(!split[j].equals(splited[j]) && !splited[j].equals("-")) break;
                        else if (j == 3) cnt++;
                    }
                }
            }
            answer[i] = cnt;
        }
        return answer;
    }
  }

  • 정확성 테스트는 전부 통과하였으나, 효율성 테스트에서 전부 시간초과로 탈락했다.
  • 어떻게든 시간을 줄여보려고 애를 썼지만, 그래도 여전히 탈락.

2차 풀이

• 카카오 2021년도 블라인드 기출문제라서 카카오의 풀이를 좀 찾아봤다.

• 생각하지도 못한 방법을 사용하는 것을 보았는데.. Map에 데이터를 넣는 방법이었다.

• key를 cppfrontendseniorchicken 처럼 중간에 모든 공백을 제거해서 넣고, 점수는 value로 list를 하나 만들어서 거기에 넣었다.

  • 왜 list로 점수를 만들었냐면, 같은 조건을 갖으면서 다른 점수를 갖는 것에 대해서 처리하기 위함이다.
  • 해당 작업을 할 때 언어, 직군, 경력, 소울푸드에 각각 -가 들어갈 수 있는 경우의 수도 같이 진행해야만 한다. 그래야 나중에 query에 - 가 들어간 경우에도 처리할 수 있으니까.

• 그 다음에는 이진 탐색을 이용해서 lower bound, 즉 일치하는 숫자가 처음 나타나는 지점을 찾는다. 그 지점을 기존 list의 사이즈에서 빼주면, 남은건 조건에 충족되는 지원자들의 수이다.

  import java.util.*;
  
   class Solution {
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
  
        // 모든 경우의 수에 대해서 map을 만들어준다.
        Map<String, ArrayList<Integer>> map = new HashMap<>();
        for (String q : info) {
            String[] s = q.split(" ");
            for (String i : new String[]{s[0], "-"}) {
                for (String j : new String[]{s[1], "-"}) {
                    for (String k : new String[]{s[2], "-"}) {
                        for (String l : new String[]{s[3], "-"}) {
                            if (map.containsKey(i + j + k + l)) {
                                ArrayList<Integer> arrayList = map.get(i + j + k + l);
                                arrayList.add(Integer.parseInt(s[s.length - 1]));
                                map.put(i + j + k + l, arrayList);
                            } else {
                                ArrayList<Integer> arrayList = new ArrayList<>();
                                arrayList.add(Integer.parseInt(s[s.length - 1]));
                                map.put(i + j + k + l, arrayList);
                            }
                        }
                    }
                }
            }
        }
        
        // 미리 정렬을 해둔다. 
        // 아래 query에서 정렬하면 이미 정렬했던 리스트를 또 한 번 더 정렬하는 일이 발생하기에 비효율적이다.
        for(String key : map.keySet()){
            Collections.sort(map.get(key));
        }
        
        // Query 조건에 맞는 개수를 판별한다.
        for (int i = 0; i < query.length; i++) {
            String[] splited = query[i].split(" and ");
            String key = splited[0] + splited[1] + splited[2] + splited[3].split(" ")[0];
            ArrayList<Integer> list = map.getOrDefault(key, new ArrayList<>());
            answer[i] = list.size() - lowerBound(list, Integer.parseInt(splited[3].split(" ")[1]));
        }
  
        return answer;
    }
  
    public int lowerBound(ArrayList<Integer> list, int value) {
        int low = 0;
        int high = list.size();
        while (low < high) {
            int mid = low + (high - low)/2;
            if (value <= list.get(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
  
        return low;
    }
  }
  

  • 모든 경우의 수를 생성할 때, dfs를 사용해서 생성하는 분도 있었다. 관련한 코드를 아래에 적어둔다.

    static void dfs(int lv) {
        if (lv == 4) {
            String str = String.join("", strings);
            if (!scoreMap.containsKey(str))
                scoreMap.put(str, new ArrayList<>());
            scoreMap.get(str).add(score);
        }else {
            strings[lv] = sInfoArr[lv];
            dfs(lv + 1);
            strings[lv] = "-";
            dfs(lv + 1);
        }
    }

소감

• 이게 실제 코테에서 나오면 내가 여기까지 생각할 수 있을까..