[프로그래머스] LV 2 메뉴리뉴얼

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

프로그래머스

접근 방법

1. 주문 배열의 길이는 2 ~ 20이고 각 주문의 길이는 2 ~ 10이다.
2. 코스 배열의 길이는 1 ~ 10이고 각 코스는 2 ~ 10이다.
3. 문제는 각 코스 길이에 맞는 요리조합을 구해야하는데 요리조합은 다음과 같은 요구사항이있다.
   1. 주어진 코스 길이와 같은 조합을 찾아야한다
   2. 가장 많이 나온 조합을 찾아야한다
   3. 동률이면 모두 추가한다
4. 그래서 먼저 코스 길이에 맞는 조합을 맵으로 랭크한다.
5. 같은 횟수로 출현한 코스조합은 다 추가한다.

코드

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	Map<String, Integer> map;
    public String[] solution(String[] orders, int[] course) {
        List<String> res = new ArrayList<>();
        
        for(int cs: course){
            map = new HashMap<>();
            for(String s : orders){
                if(s.length() < cs) continue;
                char[] c = s.toCharArray();
                Arrays.sort(c);
                comb(0,0,cs,c,new StringBuilder());
            }
            
            if(map.isEmpty()) continue;
            
            List<String> list = map.keySet().stream().sorted((s1,s2) -> map.get(s2) - map.get(s1)).collect(Collectors.toList());
            
            int max = map.get(list.get(0));
            if(max == 1) continue;
            
            res.add(list.remove(0));
            for(String s: list){
                if(map.get(s) < max) break;
                res.add(s);
            }
            
        }        
            
        return res.stream().sorted().toArray(String[]::new);
    }
    void comb(int depth, int lastIdx, int cs, char[] c, StringBuilder sb){
        if(depth == cs){
            String s = sb.toString();
            map.put(s, map.getOrDefault(s, 0)+1);
            return;
        }
        
        for(int i = lastIdx ; i < c.length ; i++){
            sb.append(c[i]);
            comb(depth+1, i+1, cs,c, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}