BruteForce,자료구조_21 카카오 메뉴 리뉴얼

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

코딩테스트 연습 - 메뉴 리뉴얼

출처: 

https://www.youtube.com/watch?v=22tBC3YXVPA&list=PL6YHvWRMtz7DhuPHdUZ0WLB5fNO729mbm&index=2 

static List<Map<String,Integer>> FoodMaps = new ArrayList<>();
    int[] MaxCnt = new int[11];
    

    void comb(char[] str, int pos, StringBuilder candi){
        if(pos >= str.length){
            int len = candi.length();
            if(len>=2){
                int cnt = FoodMaps.get(len).getOrDefault(candi.toString(),0) + 1;
                FoodMaps.get(len).put(candi.toString(),cnt);
                MaxCnt[len] = Math.max(MaxCnt[len],cnt);
            }
            return;
        }
        //선택하고
        comb(str,pos+1, candi.append(str[pos]));
        candi.setLength(candi.length()-1);
        //선택하지 않는 
        comb(str, pos+1,candi);
    }

    public String[] solution(String[] orders, int[] course){
        for(int i = 0; i <11; ++i)
            FoodMaps.add(new HashMap<String,Integer>());

        for(String str: orders){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            comb(arr,0, new StringBuilder());
        }

        List<String> list = new ArrayList<>();
        for(int len: course){
            for(Map.Entry<String,Integer> entry : FoodMaps.get(len).entrySet()){
                if(entry.getValue() >= 2 && entry.getValue() == MaxCnt[len]){
                    list.add(entry.getKey());
                }
            }
        }

        Collections.sort(list);

        String[] answer = new String[list.size()];
        for(int i = 0; i < list.size(); ++i){
            answer[i] = list.get(i);
        }
        return answer;
    }