[프로그래머스(Programmers)] 2021 KAKAO BLIND RECRUITMENT:: 순위 검색 (java)

퇴근길에 개발하기(땡진)·2021년 10월 8일

Java 알고리즘 문제풀이 추천문제 프로그래머스

알고리즘 👩🏻‍💻

목록 보기

20/53

안녕하세요. 오늘은 프로그래머스의 순위 검색 문제를 풀어보려고 합니다. 이 문제는 2021년 kakao blind recruitment에서 출제되었습니다.!

문제 링크

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

문제 풀이

dfs와 이진탐색(binary search)를 이용하는 문제였습니다.

✔ info 배열에 주어진 모든 경우의 수 저장: dfs로 구현

key가 String이고 value가 ArrayList인 해시맵을 선언한 후 dfs를 돌면서 해시맵에 모든 경우의 수를 채워줍니다.

예를 들어, info에 "java backend junior pizza 150"가 있으면, dfs를 돌면서 각 경우의 수에 따른 점수를 모두 저장합니다. 아래 표를 참고해주세요.

Key (String)	Value(ArrayList)
javabackendjuniorpizza	150
javabackendjunior-	150
javabackend--	150
java---	150
......	......

이런식으로 모든 경우의 수에 해당하는 key값들을 만들어주고, 각 value에는 지원자의 점수를 저장해주면 됩니다.

✔ hashmap의 value에 저장된 점수들 sort

Dfs를 모두 수행하고 난 후, value에 저장된 점수들을 오름차순으로 정렬해줍니다. 해당 과정은 점수 이진탐색을 수행하기 위해 꼭 필요합니다.

✔ 이진탐색 수행

query는 문의조건이 담겨있는 배열로, 각 문의조건에 해당하는 사람들의 수를 구해야 합니다. query배열에 있는 점수가 이진탐색을 통해 찾으려는 값이 되며, 2번 과정을 통해 정렬된 value들을 탐색하며 문의조건에 맞는 점수를 가진 사람이 몇 명인지 찾으면 됩니다.

전체코드

import java.util.*;

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

        for (String str : info) {
            String[] infoSpl = str.split(" ");
            dfs("", 0, infoSpl);
        }

        ArrayList<String> list = new ArrayList<>(map.keySet());

	//주소값 참조를 이용한 sort 처리
        for (String str : list) {
            ArrayList<Integer> scoreList = map.get(str);
            Collections.sort(scoreList);
        }

        for (int i = 0; i < query.length; i++) {
            String str = query[i].replaceAll(" and ", "");
            String[] strSpl = str.split(" ");
            answer[i] = binarySearch(strSpl[0], Integer.parseInt(strSpl[1]));
        }

        return answer;
    }

    private void dfs(String str, int depth, String[] arr) {
        if (depth == 4) {
            int score = Integer.parseInt(arr[4]);
            if(map.containsKey(str)) map.get(str).add(score);
            else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(score);
                map.put(str, list);
            }
            return;
        }

        dfs(str + "-", depth + 1, arr);
        dfs(str + arr[depth], depth + 1, arr);
    }

    private int binarySearch(String query, int score) {
        if(!map.containsKey(query)) return 0;
        ArrayList<Integer> list = map.get(query);
        int left = 0, right = list.size()-1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if(score > list.get(mid)) left = mid + 1;
            else right = mid - 1;
        }

        return list.size() - left;
    }
}