문제 접근

다음과 같은 절차를 따라 진행하면 풀리는 단순 구현문제다.

• 각 사람의 주문 별로 세트메뉴 종류들을 조합으로 반환해줄 수 있는 함수를 만든다.
• 세트메뉴 사이즈 별로 해당 세트메뉴가 몇번 나왔는지 기억할 Map을 만든다.
• 이 함수를 사용해서, 사람들이 주문한 메뉴들에 대해 조합을 구한다. 그 다음, 최대로 나온 횟수를 기억함.
• 마지막으로, 최대값과 동일하게 2번이상 나온 녀석들을 모두 Set에 넣어준다.
• 마지막에 정렬 한번하기

문제 풀이

import java.util.*;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        HashMap<String, Integer>[] map = new HashMap[11];
        Set<String> set = new HashSet();
        for(int i=0; i<course.length; i++) {
            int r = course[i];
            map[r] = new HashMap();
            int max = 0;
            for(int j=0; j<orders.length; j++) {
                ArrayList<String> list = find(orders[j], r);
                for(String s: list) {
                    int count = map[r].getOrDefault(s, 0)+1;
                    map[r].put(s, count);
                    max = Math.max(max, count);
                }
            }
            
            if (max < 2) continue;
            for(String s: map[r].keySet()) {
                int count = map[r].getOrDefault(s, 0);
                if (count == max) set.add(s);
            }
        }
        
        ArrayList<String> result = new ArrayList(set);
        Collections.sort(result);
        String[] answer = new String[result.size()];
        for(int i=0; i<result.size(); i++) {
            answer[i] = result.get(i);
        }
        return answer;
    }
    
    // size의 조합을 구해서 반환하는 함수
    ArrayList<String> find(String s, int size) {
        ArrayList<Character> menu = new ArrayList();
        for(int i=0; i<s.length(); i++) menu.add(s.charAt(i));
        Collections.sort(menu);
        
        ArrayList<String> set = new ArrayList();
        boolean[] isChecked = new boolean[s.length()];
        dfs(menu, set, size, 0, isChecked, new StringBuilder(), 0);
        
        return set;
    }
    
    // size의 조합을 구하는데 사용되는 재귀 함수
    void dfs(ArrayList<Character> menu, ArrayList<String> set, int size, int startIndex,boolean[] isChecked, StringBuilder sb, int curSize) {
        if (curSize == size) {
            set.add(sb.toString());
            return;
        }
        
        for(int i=startIndex; i<isChecked.length; i++) {
            if (isChecked[i]) continue;
            
            isChecked[i] = true;
            sb.append(menu.get(i));
            dfs(menu, set, size, i+1, isChecked, sb, curSize+1);
            sb.deleteCharAt(sb.length()-1);
            isChecked[i] = false;
        }
    }
}