프로그래머스 메뉴 리뉴얼

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72411 

코딩테스트 연습 - 메뉴 리뉴얼

해당 문제는 카카오 구현 문제라 그런지 푸는데 꽤나 애먹었다.
입출력 예 1번만 봤을 때는 가장 짧은 길이의 메뉴들인 "AC"와 "CDE"가 result에도 있기 때문에 길이가 작은 order에서 부터 재귀를 통해 메뉴 조합을 붙여간다고 생각했으나 입출력 2번과 3번을 보면 No.

입출력 예 2번에서는 orders에 짧은 조합에 "AD"가 없지만 result에는 "AD"가 있다. 즉, 각 order에 대해 모든 조합을 구해 가장 빈도가 높은 조합들을 선정하면 풀 수 있다.

이때 주의할 점은 orders 입출력 3번을 보면 알파벳순이 아니기 때문에 미리 정렬을 해준 배열을 넘겨야한다.
또한 최소 2명 이상의 손님에게서 주문된 구성만 답이 될 수 있음을 주의하자. 

Python

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    for menu_cnt in course:
        combi = [] 
        my_dict = dict();
        for order in orders:
            if len(order) >= menu_cnt:
                combi += list(map("".join,combinations(sorted(list(order)),menu_cnt)))
        if len(Counter(combi)) > 0: 
            maxCnt = max(Counter(combi).values())
            if maxCnt >= 2: 
                answer += [key for key, value in Counter(combi).items() if value == maxCnt]
    answer.sort()
    return answer

 

Java

import java.util.*;
import java.util.stream.*;

class Solution {
    private Map<String, Integer> map;
    private ArrayList<String> ans = new ArrayList<>();
    
    public String[] solution(String[] orders, int[] course) {
        for (int menuCnt : course) {
            map = new HashMap<>(); 
            for (String order : orders) {
                if (order.length() < menuCnt) continue;
                char[] arr = order.toCharArray();
                Arrays.sort(arr);
                boolean[] selected = new boolean[arr.length];
                combination(arr, selected, 0, menuCnt);
            }
            // 최대 고르고 저장하기
            if (map.size() > 0) {
                saveFrequentMenuCombo();
            }
        }
        Collections.sort(ans);
        return ans.toArray(new String[ans.size()]);
    }
    
    private void combination(char[] arr, boolean[] selected, int start, int r) {
        if (r == 0) {
            String s = "";
            for (int i = 0; i < arr.length; i++) {
                if (selected[i]) s += arr[i];
            }
            if(!s.equals("")) {
                if (map.containsKey(s)) {
                    map.put(s, map.get(s)+1);
                } else {
                    map.put(s, 1);
                }
            }
            return;
        }
        
        for (int i = start; i < arr.length; i++) {
            selected[i] = true;
            combination(arr, selected, i+1, r-1);
            selected[i] = false;
        }
    }
    private void saveFrequentMenuCombo() {
        int maxValue = Collections.max(map.values());
        if (maxValue < 2) return;
        List<String> frequentMenuCombo = map.entrySet().stream()
            .filter(m -> m.getValue() == maxValue)
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());
        for (String menuCombo : frequentMenuCombo) {
            ans.add(menuCombo);
        }
    }
}

풀다가 알게 된건데 Java와 Python에서 Dictionary/Map의 최대값을 구하는 함수를 쓸 때, Dictionary/Map을 작업 이후에 새로 할당하거나 clear()를 시도한다면 
Python에서는 ValueError: max() arg is an empty sequence
Java에서는 메모리 참조(?) 에러(에러문구를 캡쳐 못했습니다 ㅎㅎ;)를 마주할 수 있다.

=> 입출력 예 3번의 경우 order의 길이가 course의 길이보다 작아서 Dictionary/Map이 채워지지 않고 비어있게 되는데 데이터가 없는 곳에서 최댓값을 구하려 했기 때문에 에러가 발생하는 것이다.
따라서 `size > 0` 인가? 를 확인해야한다.