프로그래머스 - 메뉴 리뉴얼

오늘 풀어볼 문제는 ⭐메뉴 리뉴얼 이란 문제이다.

1. 문제 설명

• 손님들이 가장 많이 주문한 단품요리를 코스요리로 구성
  -> 최소 2가지 이상의 메뉴
  -> 최소 2명 이상의 손님으로부터 주문된 조합이어야 함
  -> 가장 많은 횟수의 단품요리가 해당 코스 요리로 선정됨 (최대 횟수가 같다면 모두 코스요리로 선정)

2. 입출력

2.1 입력

• [주문목록 : orders]
  -> 손님은 최소 2가지 최대 10가지 메뉴 주문
  -> 중복 주문은 하지 않음
  -> 최대 손님 20명
• [코스요리 개수 : course]
  -> 원하는 코스요리 가지수가 오름차순으로 입력됨.

2.2 출력

• 사전순으로 오름차순 정렬해 return

3. 알고리즘

1. 메뉴들 조합 값 담을 Map<String, Integer> johap 만들기

2. 가장 많이 주문된 횟수를 담을 maxOrder[] 배열 생성
   -> 주문의 최대 개수가 10개, 조합의 최대 개수 역시 10개 이므로 11개의 원소 배열로 형성

3. orders[i]의 값 정렬 후, 해당 문자열 전역변수에 저장

4. 조합 찾기
   -> comb(int now, int cnt, String s, int course) dfs 함수
   -> 만약 현재 cnt==course 라면, Map.put(s, s.get(s)+1 );
   -> 아니라면, for 문으로 현재 전역변수 길이만큼 for문으로 comb 함수 돌리기

5. Map을 전체적으로 다 돌며 조건에 해당하는 것만 answer 배열에 담기
   -> 조합 메뉴의 길이가 orders 배열에 있어야 함
   -> Map에 저장된 value값이, maxOrders[orders[i]]와 일치해야함
   -> maxOrders[orders[i]], 즉 해당 조합의 최대 주문 횟수가 2 이상이어야 함

6. 정렬 후 정답 return

4. 코드

import java.util.*;

class Solution {
    static String str;
    static Map<String, Integer> johap;
    static int [] maxOrder;
    public String[] solution(String[] orders, int[] course) {
        johap = new HashMap<>();
        maxOrder = new int[11];
        
        for(String s : orders) {
            char [] cArr = s.toCharArray();
            Arrays.sort(cArr);
            str = "";
            for(char c : cArr){
                str +=c;
            }
            
            for(int courseNum : course){
                comb(0,0,"",courseNum);
            }
            
        }
        
        
        List<String> answer = new ArrayList<>();
        
        for (String s : johap.keySet()) {
            for(int courseNum : course){
                if(s.length()==courseNum && johap.get(s) == maxOrder[courseNum] && maxOrder[courseNum] >=2 ) answer.add(s); {
                }
            }
        }
        
        Collections.sort(answer);
        
        return answer.toArray(new String[0]);
    }
    
    static void comb(int now, int cnt, String s, int course) {
        if(cnt==course) {
            johap.put(s, johap.getOrDefault(s, 0)+1);
            maxOrder[course] = Math.max(johap.get(s), maxOrder[course]);
            return;
        }
        
        for(int i=now; i<str.length(); i++) {
            comb(i+1, cnt+1, s+str.charAt(i), course);
        }
    }
}