[JAVA] 2021 KAKAO BLIND RECRUITMENT 【메뉴 리뉴얼】

---

백트래킹으로 음식 조합을 구한 뒤, 음식 조합 별 주문 횟수를 구한다. (bt() 메서드 사용)

 

<음식 조합, 주문횟수> 와 같이 입력될 것이다.

 

그리고 이 맵을 이용해서, <코스사이즈, 코스 사이즈의 최대 주문횟수> 를 구한다. (getMaxMenu())

 

그리고 코스사이즈별 최대 주문횟수를 알게 됐으므로,

 

코스 사이즈와 음식 조합의 길이가 일치하면서 [주문횟수와 최대 주문횟수가 일치한 것 & 2번 이상 주문 된]것의 Max 값을 리스트 자료구조인 ans에 기록한다.

 

정렬한 뒤, 배열로 변환해서 반환한다

 

---

import java.util.*;
class Solution {
    HashMap<String,Integer> map;
    HashMap<Integer,Integer> max;
    List<String> ans;
    StringBuilder sb;
    public String[] solution(String[] orders, int[] course) {
        map = new HashMap<>();
        max = new HashMap<>();
        ans = new ArrayList<>();
        sb = new StringBuilder();

        for(String order : orders){
            for(int num : course){
                bt(order,num,0);
            }
        }

        getMaxMenu();

        getAns();

        return ans.toArray(new String[ans.size()]);
    }

    void getAns(){
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            int len  = entry.getKey().length();
            if(max.get(len)==entry.getValue() && entry.getValue()>=2){
                ans.add(entry.getKey());
            }
        }
        Collections.sort(ans);

    }

    void getMaxMenu(){
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            int len  = entry.getKey().length();
            max.put(len,Math.max(max.getOrDefault(len,0),entry.getValue()));
        }
    }

    void bt(String order, int size, int start){
        if(sb.length()==size){
            char[] arr = sb.toString().toCharArray();
            Arrays.sort(arr);
            String menu = new String(arr);
            map.put(menu,map.getOrDefault(menu,0)+1);
            return;
        }
        for(int i=start;i<order.length();i++){
            String menu = String.valueOf(order.charAt(i));
            if(sb.indexOf(menu)>=0){
                continue;
            }
            sb.append(menu);
            bt(order,size,i+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}