[Programmers] 순위 검색 / ⭕

프로그래머스

 

1. 제출 코드 (3시간 20분 45초 / 맵, 정렬, 이분탐색)

import java.util.*;

class Solution {
    static String[] lang = {"cpp", "java", "python"};
    static String[] role = {"backend", "frontend"};
    static String[] career = {"junior", "senior"};
    static String[] dish = {"chicken", "pizza"};
    static Map<String, ArrayList<Integer>> m = new HashMap<>();
    static int cnt = 0;
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        
        Arrays.sort(info, (o1, o2) -> {
            String[] t1 = o1.split(" ");
            String[] t2 = o2.split(" ");
            return Integer.parseInt(t1[4]) - Integer.parseInt(t2[4]);
        });
        
        for(int i = 0; i < info.length; i++) {
            String[] t = info[i].split(" ");
            ArrayList<Integer> ta = m.get(t[0] + t[1] + t[2] + t[3]);

            if(ta == null) {
                m.put(t[0] + t[1] + t[2] + t[3], new ArrayList<>(Arrays.asList(Integer.parseInt(t[4]))));
            } else {
                ta.add(Integer.parseInt(t[4]));
                m.put(t[0] + t[1] + t[2] + t[3], ta);
            }
        }
        
        for(int i = 0; i < query.length; i++) {
            String[] t = query[i].split(" and ");
            int score = Integer.parseInt(t[3].split(" ")[1]);
            t[3] = t[3].split(" ")[0];
            cnt = 0;
            backtracking(t, "", 0, score);
            answer[i] = cnt;
        }

        return answer;
    }
    
    public static int binarySearch(ArrayList<Integer> t, int score) {
        int left = 0;
        int right = t.size() - 1;
        int mid = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            if(t.get(mid) < score) left = mid + 1;
            else if (t.get(mid) >= score) right = mid - 1;
        }
        return t.size() - left;
    }
    
    public static void backtracking(String[] t, String word, int idx, int score) {
        if(idx == 4) {
            ArrayList<Integer> temp = m.get(word);
            if(temp != null) {
                cnt += binarySearch(temp, score);
            }
            return;
        }
        if(t[idx].equals("-")) {
            if(idx == 0) {
                for(int i = 0; i < 3; i++) {
                    backtracking(t, word + lang[i], idx + 1, score);
                }   
            } else if(idx == 1) {
                for(int i = 0; i < 2; i++) {
                    backtracking(t, word + role[i], idx + 1, score);
                }   
            } else if(idx == 2) {
                for(int i = 0; i < 2; i++) {
                    backtracking(t, word + career[i], idx + 1, score);
                }   
            } else {
                for(int i = 0; i < 2; i++) {
                    backtracking(t, word + dish[i], idx + 1, score);
                }   
            } 
        } else {
            backtracking(t, word + t[idx], idx + 1, score);
        }
    }
}

 

 

2. 구현 로직

1. info와 query의 크기를 봤을 때, N^2의 시간 복잡도는 될 수 없었다. NlogN 이하의 시간 복잡도를 가져야 하기에 Map을 사용했다.
2. info의 점수를 추후 이분 탐색에 활용하기 위해 정렬
3. info의 원소를 탐색하면서 나올 수 있는 모든 조합을 map에 저장
   1. info[i]를 split하여 점수와 그 외의 값들을 분리
   2. 개발언어, 직군, 경력, 소울푸드를 합친 문자열을 key로 두고 value를 Arraylist를 만들어 삽입(이때, 위에서 정렬이 이뤄졌기에 오름차순으로 들어감)
4. query도 마찬가지로 탐색을 하는데 점수와 그 외의 값들을 분리
5. query를 통해 나올 수 있는 경우의 수를 모두 찾기 위해 bactracking 함수 실행
   1. 만약, 현재의 idx가 "-"라면 각 항목의 모든 원소가 나올 수 있으므로 for문을 통해 하나씩 대입
   2. 위 경우가 아니라면 현재의 word 값에 t[idx]를 더해서 다음 순서로 넘김
   3. idx == 4는 점수를 제외한 모든 항목이 입력될 경우를 나타내는데, 이때 word의 값을 map에서 검색하여 해당되는 점수들을 가져온다.
   4. 기존에는 for문을 이용해서 score보다 큰 값이 있다면 cnt를 +1 해줬는데 효율성을 통과하지 못했다.
   5. 다시 생각해보니, 모든 info가 동일한 값을 가지면 최악의 경우가 되고 이는 n^2의 시간복잡도가 나오게된다. 이를 해결하기 위해 이분탐색을 진행했다.
   6. 이분 탐색을 통해 나온 left는 score보다 작은 원소들이므로 t.size() - left를 통해 score보다 큰 값의 개수를 추출
   7. 이후, 모든 경우의 수에서 나오는 cnt를 더해서 query에 대한 정답 추출

 

3. 회고

• 처음부터 어떻게 구현을 할지 생각하고 진행하는 습관을 가져야할 거 같다.