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

이 문제는 다음과 같은 순서로 풀었다.

1. 코스 별로 조합을 만들어야 한다. 이 때 “코스” 는 각 코스를 구성하는 “메뉴의 개수”다.
2. 주문 별로 조합을 만들어야 한다.
   • 조합을 만들 때면, 주어진 주문 String order 에서, 개수 별로 만들 수 있는 조합을 만들어야 하기 때문에 반복문이 아닌 "재귀"를 사용해야 한다고 생각했다
   • 이 때, 동일한 문자열을 반복해서 생성할 필요가 없다고 생각하였기 때문에, recur1 은 idx 0 부터, recur2 는 "recur1 에서 선택한 위치 + 1" 부터 .... 로 생각했다.
   • 그러면서도, 특정 길이의 조합 문자열을 만들어야 하는 것 이기 때문에, 현재 재귀함수가 호출된 시점 까지 선택한 메뉴 개수 cnt 와, 현재 만들어야 하는 조합을 이뤄야 하는 메뉴의 개수 c, 그리고 현재 주어진 주문에 속한 전체 메뉴의 개수 order.length() 를 사용해서, 계속해서 진행할 경우, 길이 c 인 조합을 만들 수 있는지 검증할 수 있도록 하였다
3. 만들어진 조합들은 Map 을 통해 조합의 개수를 관리한다.
   1. 이 때, 주어진 orders 의 각 문자열들을 “사전순으로 주어지지 않았다!!”
   2. 따라서, 만들어진 조합의 문자열은 → 또 다시 사전순으로 정렬하여 → Map 에 저장하는 과정이 필요하다
   3. 추가적으로 나는, 각 코스별(n 개로 만드는 조합 별) 로 등장 개수의 max 를 저장하여 관리하였다
4. Map 의 모든 엔트리들을 iterate 하면서, 2 번 이상 등장 하면서, n 개로 만든 조합에서 최대로 등장한 문자열 일 경우 → ans 에 추가 하였다.
5. 마지막에는 ans 를 정렬하였다. ( Collections, Arrays 모두 문자열에 대해선 기본적으로 사전순 정렬을 하고 있다 )

import java.util.*;
import java.util.Map.Entry;

class Solution {
    // 각 order 의 character 들이 오름차순으로 주어지는 것은 아니다 ! 
    private int[] max = new int[11]; // 각 개수 당 -> max 등장횟수를 저장하는 배열

    private Map<String, Integer> map = new HashMap<>();

    private StringBuilder sb = new StringBuilder("");

    public String[] solution(String[] orders, int[] course) {
        for (int c : course) {
            for (String order : orders) {
                find(order, c, 0, 0);
            }
        }

        List<String> list = new ArrayList<>(orders.length);

        for (Entry<String, Integer> e : map.entrySet()) {
            if (e.getValue() >= 2 && e.getValue() == max[e.getKey().length()]) {
                list.add(e.getKey());
            }
        }
        
        Collections.sort(list);

        return list.toArray(new String[]{});
    }
    
    private void find(String order, int c, int cnt, int cur) {
        if (cnt == c) {
            String str = sb.toString();
            int numb = map.getOrDefault(str, 0) + 1;
            map.put(str, numb);

            max[c] = Math.max(max[c], numb); // max update
            return;
        }

        for (int i = cur; i <= order.length() - (c - cnt); i++) {
            sb.append(order.charAt(i));
            find(order, c, cnt + 1, i + 1);
            sb.delete(cnt, cnt + 1);
        }
    }
}