문제

메뉴 리뉴얼

풀이

풀이를 생각하지 못해서 검색하여 풀었다 이문제는 손님들이 주문한 메뉴들 중 2번 이상 시킨 메뉴들을 조합으로 코스요리를 짜는 내용이다. 실생활에서도 유용하게 쓰일 알고리즘 문제라고 생각한다
해당 문제는 DFS로 풀이 되는 문제이다.

1. 손님들이 주문한 메뉴들을 재정렬 한다

		for (int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }

해당 메뉴들을 정렬하는 이유는 이후에 dfs로 조합이 되고 난 후에도 정렬을 해야하는데 후에 정렬을 하면 좀 더 많은 복잡도가 걸리기 때문이다. XA 혹은 AX 둘다 같은 조합인데 이경우에 같은 경우라고 판단하게 해주려면 알파벳 순서를 정렬을 해주면 더 판단하기 편하기 때문이다

2. 조합

	/**
     * 메뉴 조합
     * @param menu 메뉴 이름
     * @param order 다음 주문
     * @param c 메뉴 개수
     */
    private static void combination(String menu, String order, int c) {
        if (c == 0) {
            h.put(menu, h.getOrDefault(menu, 0) + 1);
            return;
        }

        for (int i = 0; i < order.length(); i++) {
            combination(menu + order.charAt(i), order.substring(i + 1), c - 1);
        }
    }

글자를 조합해준다. 이때 메뉴 0이 되면 조합할 수 있는 메뉴가 없다는 것이므로 조합이 종료 된다

3. 코스 요리 개수 별로 가장 많이 조합된 메뉴를 걸러낸다

			if (!h.isEmpty()) {
                List<Integer> cList = new ArrayList<>(h.values());
                int max = Collections.max(cList);
                if (max > 1) {
                    for (String menu : h.keySet()) {
                        if (h.get(menu) == max) {
                            answer.add(menu);
                        }
                    }
                }
                h.clear();
            }

hashmap.values()로 리스트 를 생성하여 max value가 2 이상이 되면 hashmap에 있는 키들중 max값에 해당하는 것을 answer에 넣어준다.

전체 코드

전체 코드