[프로그래머스]메뉴 리뉴얼-java

 

📌풀이

1. 각 주문을 알파벳 순서로 정렬한 뒤, 조합을 생성한다.

2. 생성된 조합이 나타나는 횟수를 기록한 뒤, 각 길이에 대해 가장 많이 주문된 조합을 찾는다.

3. 최종적으로 모든 결과를 사전 순으로 정렬하여 반환한다.

최악의 경우 10*20*2^10

 

📌코드

import java.util.*;

class Solution {
    public static void getCombination(Map<String, Integer> ret, String str, int N, int depth, int start, char[] cur){
        if(depth>=N){
            if(!ret.containsKey(new String(cur))) ret.put(new String(cur), 0);
            ret.put(new String(cur), ret.get(new String(cur))+1);
            return;
        }    
        
        for(int i=start, LEN=str.length(); i<LEN; i++){
            cur[depth]=str.charAt(i);
            getCombination(ret, str, N, depth+1, i+1, cur);
        }
    }
    
    public String[] solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        
        for(int c : course) {
            Map<String, Integer> map = new HashMap<>();
            for(String order : orders){
                char[] tmp = order.toCharArray();
                Arrays.sort(tmp);
                String sortedStr = new String(tmp);
                getCombination(map, sortedStr, c, 0, 0, new char[c]);
            }
            
            int maxVal = 2;
            for(int val : map.values()){
                if(val>maxVal) maxVal = val;
            }
            
            for(String key : map.keySet()){
               if(map.get(key)==maxVal) answer.add(key); 
            }
        }
        
        Collections.sort(answer);
        
        return answer.toArray(new String[0]);
    }
}