Lv 2. 메뉴 리뉴얼

코드 흐름

• map: 메뉴 조합을 키로, 그 조합이 등장한 횟수를 값으로 저장하는 해시맵선언.
  max: 현재 탐색 중인 코스 길이에서 가장 많이 등장한 메뉴 조합의 빈도를 저장하는 변수.
• DFS 메서드: 주어진 order에서 가능한 메뉴 조합을 생성하고, 그 조합을 map에 저장하여 등장 횟수를 기록.
  
  • order: 현재 탐색 중인 주문의 메뉴 문자열.
  • index: 현재 탐색 중인 문자열의 인덱스.
  • key: 현재까지 생성된 메뉴 조합 문자열.
  • end: 탐색할 메뉴 조합의 목표 길이.
  • depth: 현재 조합의 길이.
  • 조합의 길이가 목표 길이(end)에 도달하면, 해당 조합을 map에 저장하고 max를 업데이트.
    그렇지 않으면, 다음 인덱스부터 시작하여 재귀적으로 DFS를 호출하여 메뉴 조합을 생성.
• solution 메서드:
  • 입력된 주문(orders)과 코스 길이(course)를 바탕으로 인기 있는 메뉴 조합탐색.
    
    • orders: 각 손님의 주문을 나타내는 문자열 배열.
    • course: 찾고자 하는 메뉴 조합의 길이 배열.
      
      1. course 배열을 순회하면서, 각 길이 c에 대해 다음을 수행
      2. map과 max를 초기화하여 새로운 코스 길이의 조합을 저장할 준비.
      3. 각 주문(or)에 대해 메뉴를 정렬하고, DFS를 호출하여 해당 길이의 모든 메뉴 조합을 탐색.
      4. DFS가 끝난 후, map에서 max와 동일한 빈도를 가진 조합을 결과 리스트(ans)에 추가.
      5. 모든 코스 길이에 대해 탐색이 끝나면, 결과 리스트를 정렬하고 문자열 배열로 변환하여 반환.

import java.util.*;

class Solution {
    Map<String,Integer> map = new HashMap<>();
    int max = 0 ;
    public void DFS (String order, int index, String key, int end,int depth){
        if(end == depth){
            map.put(key,map.getOrDefault(key,0)+1);
            max = Math.max(map.get(key),max);
        }
        for(int i = index + 1 ; i < order.length() ; i++){
            DFS(order,i,key+order.charAt(i),end,depth+1);
        }
    }
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> ans = new ArrayList<>();
        for(int c : course){
            map = new HashMap<>();
            max = 0;
            for(String or: orders){
                char[] o = or.toCharArray();
                Arrays.sort(o);
                String order = new String(o);
                DFS(order,-1,"",c,0);
            }
            for(String key : map.keySet()){
                int value = map.get(key);
                if(value > 1 && max == value)
                    ans.add(key);
            }
        }
        Collections.sort(ans);
        String[] answer = ans.toArray(new String[ans.size()]);
        return answer;
    }
}