[2021 카카오 블라인드]순위 검색★

📍 문제 설명

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

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

 

💡 접근

꽤 많이 까다로웠던 문제였다. 정확성 밖에 맞추지 못했는데 효율성을 위해서는 이분 탐색을 사용해야 한다고 한다.

이분탐색 풀이법은 타 블로그 참고해서 다시 풀어봐야겠다.

 

 

👩‍💻 코드

import java.util.*;

class Solution {
    static HashMap<String, List<Integer>> map;
    static boolean[] visited;
    static int m;
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        for(int i = 0; i < query.length; i++) query[i] = query[i].replace(" and ", "");

        map = new HashMap<>();
        for(int i = 0; i < info.length; i++) {
            String[] split = info[i].split(" ");
            visited = new boolean[4];
            for(m = 0; m <= 4; m++) {
                DFS(0, 0, split);
            }
        }

        for(int i = 0; i < query.length; i++) {
            String[] split2 = query[i].split(" ");
            if(map.containsKey(split2[0])) {
                for(int j = 0; j < map.get(split2[0]).size(); j++) {
                    if(map.get(split2[0]).get(j) >= Integer.parseInt(split2[1])) answer[i]++;
                }
            }
        }

        return answer;
    }

    private void DFS(int L, int s, String[] split) {
        if(L == m) {
            String[] clone = split.clone();
            for(int i = 0; i < 4; i++) {
                if(visited[i]) clone[i] = "-";
            }
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < 4; i++) {
                sb.append(clone[i]);
            }
            if(!map.containsKey(sb.toString())) {
                List<Integer> list = new ArrayList<>();
                map.put(sb.toString(), list);
            }
            map.get(sb.toString()).add(Integer.parseInt(split[4]));

        }
        else {
            for (int i = s; i < 4; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    DFS(L + 1, i + 1, split);
                    visited[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        String[] info = {"java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"};
        String[] query = {"java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"};
        s.solution(info, query);
    }
}
//2 21 213 2134