[JAVA 문제 풀이] 377. 메뉴 리뉴얼

내가 작성한 코드

import java.util.*;

class Solution {
    // 각 조합 문자열의 등장 횟수를 저장할 맵
    Map<String, Integer> combinationCount;

    public String[] solution(String[] orders, int[] course) {
        List<String> result = new ArrayList<>(); // 최종 결과를 저장할 리스트

        // 각 코스 길이에 대해 반복
        for (int c : course) {
            combinationCount = new HashMap<>(); // 코스 길이마다 초기화
            int maxCount = 0; // 현재 코스 길이에서 가장 많이 등장한 조합의 등장 횟수

            // 모든 주문에 대해 조합 생성
            for (String order : orders) {
                char[] chars = order.toCharArray();
                Arrays.sort(chars); // 조합 생성을 위한 알파벳 정렬
                combine("", chars, 0, c); // 조합 생성 시작
            }

            // 가장 많이 등장한 조합의 등장 횟수 확인
            for (Map.Entry<String, Integer> entry : combinationCount.entrySet()) {
                int count = entry.getValue();
                if (count >= 2) { // 최소 2명 이상 주문한 경우만 유효
                    maxCount = Math.max(maxCount, count);
                }
            }

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

        Collections.sort(result); // 최종 결과를 사전 순 정렬

        return result.stream()
                .toArray(String[]::new); // String 배열로 변환
    }

    // 조합을 재귀적으로 생성하는 함수
    private void combine(String prefix, char[] order, int idx, int len) {
        // 원하는 길이만큼 조합이 만들어졌을 경우 map에 추가
        if (prefix.length() == len) {
            combinationCount.put(prefix, combinationCount.getOrDefault(prefix, 0) + 1);
            return;
        }

        // 현재 인덱스부터 끝까지 반복하며 조합 생성
        for (int i = idx; i < order.length; i++) {
            combine(prefix + order[i], order, i + 1, len);
        }
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> map; // 메뉴 조합과 그 조합의 주문 횟수를 저장하는 맵
    static int m; // 가장 많이 주문된 조합의 횟수

    public String[] solution(String[] orders, int[] course) {
        PriorityQueue<String> pq = new PriorityQueue<>(); // 정답을 저장할 큐

        for (int i = 0; i < course.length; i++) {
            map = new HashMap<>();
            m = 0;

            // 각 주문에 대해 조합을 찾기
            // course[i]는 현재 목표 조합의 메뉴 개수
            // orders[j]는 현재 주문 문자열
            for (int j = 0; j < orders.length; j++) {
                find(0, "", course[i], 0, orders[j]);
            }

            // 현재 course[i]에 대해 가장 많이 주문된 조합을 찾기
            for (String s : map.keySet()) {
                if (map.get(s) == m && m > 1) {
                    pq.offer(s);
                }
            }
        }

        // 큐를 배열로 변환
        String ans[] = new String[pq.size()];
        int k = 0;

        while (!pq.isEmpty()) {
            ans[k++] = pq.poll();
        }

        return ans;
    }

    // cnt: 현재 조합에 포함된 메뉴의 개수
    // str: 현재 조합에 포함된 메뉴 문자열
    // targetNum: 목표 조합의 메뉴 개수
    // idx: 현재 탐색할 메뉴의 인덱스
    // word: 현재 주문 문자열
    static void find(int cnt, String str, int targetNum, int idx, String word) {
        // 현재 조합의 메뉴 개수가 목표 개수와 같으면
        if (cnt == targetNum) {
            char[] c = str.toCharArray(); // 현재 조합의 메뉴 문자열을 문자 배열로 변환
            String temps = ""; // 현재 조합의 메뉴 문자열을 저장할 변수

            Arrays.sort(c); // 조합을 사전순으로 정렬

            // 현재 조합의 메뉴 문자열을 temps에 저장
            for (int i = 0; i < c.length; i++)
                temps += c[i];

            // 현재 조합의 메뉴 문자열을 맵에 저장하고, 해당 조합의 주문 횟수를 증가시킴
            map.put(temps, map.getOrDefault(temps, 0) + 1);
            m = Math.max(m, map.get(temps)); // 가장 많이 주문된 조합의 횟수를 업데이트

            return;
        }

        // 현재 인덱스부터 시작하여 가능한 모든 조합을 찾기
        for (int i = idx; i < word.length(); i++) {
            char now = word.charAt(i);

            find(cnt + 1, str + now, targetNum, i + 1, word);
        }
    }
}