[Programmers Lv.2][순위 검색][java]

문제 링크

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

프로그래머스

---

조건

지원서 작성 시, 4가지 항목을 선택해야 함
개발 언어 - cpp, java, python
직군 - backend, frontend
경력 구분 - junior, senior
소울 푸드 - chicken, pizza

“-” 은 고려하지 않겠다는 의미

코테 결과를 분석해서 지원자들의 지원 조건을 선택 시 해당 조건에 맞는 지원자가 몇 명인지 알 수 있는 도구

ex. java 로 참여해서 backend 직군을 선택하고 junior 경력이면서 pizza를 선택한 사람 중 코테 점수가 50점 이상인 사람 몇 명?

결론 : [조건] 을 만족하는 사람 중 코테 점수를 x 점 이상 받은 사람은 몇 명인가

 

알고리즘 

1. 지원자 정보로 조합하기
2. 해당 조건에 대한 지원자 점수 정렬
3. 해당 쿼리에 대해 이분 탐색으로 코테 점수에 맞는 지원자 수 저장 후 리턴

 

전체 코드

package com.example.javaproject3.psstudy;

import java.util.*;

public class Solution43238 {
    // ex. {"javabackendjuniorpizza" : {100, 80, 70}} 이런 식으로 저장되어 있음
    static HashMap<String, List<Integer>> hm = new HashMap<>();

    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        for (String in : info)
            combination("", 0, in.split(" ")); // 지원자 정보를 분리한 후 조합 메소드 호출

        for (String key : hm.keySet()) // 점수 정렬
            Collections.sort(hm.get(key));

        for (int i = 0; i < query.length; i++) {  // 점수 조건 탐색 위해 이분 탐색
            String[] tmp = query[i].replaceAll(" and ", "").split(" ");  // and 를 없애고 [조건, 점수] 배열로 분리
            answer[i] = hm.containsKey(tmp[0]) ? binarySearch(tmp[0], Integer.parseInt(tmp[1])) : 0; // hashmap 에 있으면 이분 탐색 메소드 호출해서 점수 저장, 없으면 0 저장
        }
        return answer;
    }

    public int binarySearch(String str, int score) {  // str 과 점수로 이분 탐색
        List<Integer> list = hm.get(str);
        int left = 0, right = list.size() - 1;

        // ex. {100,80,70,50} 중 60보다 큰 점수를 받은 지원자 수 = 리턴이 3이 나와야 함
        // left = 0, right = 3, mid = 1 으로 시작
        while (left <= right) {
            int mid = (left + right) / 2;

            if (list.get(mid) < score)  // 해당 지원자의 점수보다 score 가 크다면
                left = mid + 1;  // mid 이전의 지원자 점수는 해당하지 않음
            else right = mid - 1;
        }
        return list.size() - left;  // str 에 해당하는 점수의 총 개수에서 점수보다 크거나 같은 left 뺀 값 (지원자 수) 리턴
    }

    public void combination(String str, int len, String[] arr) {
        if (len == 4) {
            if (!hm.containsKey(str)) {  // str 이 hashmap 에 포함되어 있지 않으면
                hm.put(str, new ArrayList<>());
            }
            hm.get(str).add(Integer.parseInt(arr[4])); // str 에 해당하는 지원자 점수 hashmap 에 추가
            return;
        }
        combination(str + "-", len + 1, arr);  // 조건을 고려하지 않은 경우의 재귀 호출
        combination(str + arr[len], len + 1, arr); // 조건을 고려하는 경우의 재귀 호출 

    }

 
}

 

코드 리팩토링

public void combination(String str, int len, String[] arr) {
    if (len == 4) {
        hm.computeIfAbsent(str, k -> new ArrayList<>()).add(Integer.parseInt(arr[4]));
        return;
    }
    combination(str + "-", len + 1, arr);
    combination(str + arr[len], len + 1, arr);
}