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

⭐ 문제링크

1. 문제 요약

• "스카피"는 가장 많이 함께 주문된 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

  • 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 후보에 포함하기로 했습니다.
  • 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 한다.

• 입력 : orders 배열
  

• 입력 : course 배열
  : 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열

• 출력 : 스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return

---

[입출력 예시]

2. 접근법

• course에 있는 숫자들(코스 길이)을 하나씩 선택하면서 반복

• 각 주문을 사전 순으로 정렬하고, 그 주문에서 만들 수 있는 조합을 DFS로 하나하나 생성.

• 만들어진 조합을 HashMap<String, Integer>에 저장하면서 몇 번 등장했는지 카운팅.

• 조합 중에서 등장 횟수가 가장 높은 값(max)만 골라서 최종 결과에 넣기

• 최종 결과는 사전순으로 반환

3. 코드

import java.util.*;

class Solution {
    private Map<String, Integer> comboCount; // 조합 -> 등장 횟수
    private List<String> result;

    public String[] solution(String[] orders, int[] course) {
        result = new ArrayList<>();

        for (int len : course) { //course 길이별로 반복하며 조합 생성
            comboCount = new HashMap<>();

            for (String order : orders) { // 주문 하나씩 처리 + 정렬
                if (order.length() < len) continue; //주문이 원하는 코스보다 짧으면 조합 불가 → skip 
                char[] items = order.toCharArray();
                Arrays.sort(items); // 사전 순 정렬
                dfs(items, len, 0, new StringBuilder());
            }

            // 최다 등장 횟수 계산
            int maxCount = comboCount.values().stream()
                    .filter(v -> v >= 2)
                    .max(Integer::compareTo)
                    .orElse(0);

            // 등장 횟수가 maxCount인 조합만 결과에 추가
            for (Map.Entry<String, Integer> entry : comboCount.entrySet()) {
                if (entry.getValue() == maxCount && maxCount >= 2) {
                    result.add(entry.getKey());
                }
            }
        }

        Collections.sort(result);
        return result.toArray(new String[0]);
    }

    private void dfs(char[] items, int targetLen, int start, StringBuilder sb) {
        if (sb.length() == targetLen) {
            String combo = sb.toString();
            comboCount.put(combo, comboCount.getOrDefault(combo, 0) + 1);
            return;
        }

        for (int i = start; i < items.length; i++) {
            sb.append(items[i]);
            dfs(items, targetLen, i + 1, sb);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
    }
}

4. 상세 코드

조합 생성 dfs

  private void dfs(char[] items, int targetLen, int start, StringBuilder sb) {
        if (sb.length() == targetLen) {
            String combo = sb.toString();
            comboCount.put(combo, comboCount.getOrDefault(combo, 0) + 1);
            return;
        }

        for (int i = start; i < items.length; i++) {
            sb.append(items[i]);
            dfs(items, targetLen, i + 1, sb);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
    }

• 현재 조합 길이가 targetLen이면 map에 count 증가
• 그렇지 않으면 메뉴 하나 추가하고 DFS 재귀 호출
• 종료 후에는 sb rollback해서 백트래킹 (조합 복원)