[프로그래머스][JAVA] 메뉴 리뉴얼 (조합, 백트래킹)

1. orders배열의 order들을 toCharArray()로 char[]로 변환 후 Arrays.sort(char[]) 후에 String.valueOf(char[])로

알파벳 순으로 정렬된 주문 요리순서로 바꿈

(이거 안해주면 나중에 map으로 누적시킬 때 "XY" "YX" 이런 요리 조합이 따로 누적됨)

 

2. comb 메서드는 계속 하면 indexOutOfRange뜨다가 결국 완성함

 

3. combOrder 메소드의 마지막 parameter인 int PreIdx가 핵심이었는데 이걸 안해주면

XYZ의 조합에서 ZZZ

AB 조합에서 BB

이런 것이 나옴

 

4. mostOrderNum int[]을 통해 n개 조합의 최다 주문된 횟수를 mostOrderNum[n]에 Math.max를 통해 계속 갱신시켜줄것

 

 

import java.util.*;

class Solution {
    private static Map<String, Integer> menuMap;
    private static int[] mostOrderNum; // 코스요리 중 가장 많이 주문된 횟수 (index는 코스요리 조합 수임)
    
    public String[] solution(String[] orders, int[] course) {
        menuMap = new HashMap<>();
        mostOrderNum = new int[11];

        
        for(String order : orders){
            // System.out.println(order);
            char[] chArr = order.toCharArray();
            Arrays.sort(chArr);
            order = String.valueOf(chArr);
            // System.out.println(order);
            
            analyzeCourseMenu(order);
        }
        
        List<String> resultList = new ArrayList<>();
        
        for(Map.Entry<String,Integer> e : menuMap.entrySet()){
            String finalMenu = e.getKey();
            int finalMenuAccum = e.getValue();
            // System.out.println(e.getValue()+" "+e.getKey());
            
            for(int c : course){
            // 코스요리 메뉴의 주문 횟수가 2회 이상이고, c개의 요리들의 조합이고, 주문횟수가 c개 요리들 중 최다주문 횟수와 일치
                if(finalMenuAccum>=2 && finalMenu.length()==c && finalMenuAccum==mostOrderNum[c]){
                    resultList.add(finalMenu);
                }
            }
        }
        Collections.sort(resultList);
        // resultList.forEach(System.out::println);
        
        String[] answer = new String[resultList.size()];
        for(int i=0; i<resultList.size(); i++){
            answer[i] = resultList.get(i);
        }
        
        return answer;
    }
    
    private void analyzeCourseMenu(String order){
        for(int combNum=2; combNum<=order.length(); combNum++){
            
            // visited 데이터는 필요 없는듯..
            // boolean[] visited = new boolean[order.length()];
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<order.length(); i++){
                sb.append(order.charAt(i));
                // visited[i] = true;
                
                combOrder(order, sb, combNum, 1, i);
                
                sb.deleteCharAt(sb.length()-1);
                // visited[i] = false;
            }

        }
    }
    
    private void combOrder(String order, StringBuilder sb, int combNum, int preNum, int preIdx){
        if(preNum==combNum){
            // System.out.println((preNum)+" "+sb.toString());
            String finalMenu = sb.toString();
            int finalMenuAccum = menuMap.getOrDefault(finalMenu, 0)+1;
            menuMap.put(finalMenu, finalMenuAccum);
            mostOrderNum[preNum] = Math.max(mostOrderNum[preNum], finalMenuAccum);
            
            return;
        }
        for(int i=preIdx+1; i<order.length(); i++){
            // if(visited[i]) continue;
            sb.append(order.charAt(i));
            // visited[i] = true;
            
            combOrder(order, sb, combNum, preNum+1, i);
            sb.deleteCharAt(sb.length()-1);
            // visited[i] = false;
            
        }
        
    }
        
//     private class MenuComb{
//         String menuComb;
//         int accum;
        
//         public MenuComb(String menuComb, int accum){
//             this.menuComb = menuComb;
//             this.accum = accum;
//         }   
//     }
}​