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

문제 링크

메뉴 리뉴얼

풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public String[] solution(String[] orders, int[] course) {

        HashMap<String, Integer> courseMap = new HashMap<>();
        for (String order : orders) {
            char[] chars = order.toCharArray();
            Arrays.sort(chars);
            boolean[] visited = new boolean[chars.length];
            for (int i : course) {
                if(order.length() >= i) combination(chars, visited, courseMap, 0, i);
            }
        }

        ArrayList<String> courseList = new ArrayList<>();
        // 같은 길이의 메뉴중에서, 가장 주문횟수가 많은 메뉴를 뽑아야한다. 
        for(int i : course){
            int max = 0;
            for(String combi : courseMap.keySet()){
                if(combi.length() == i && courseMap.get(combi) > 1){
                    max = Math.max(max, courseMap.get(combi)) == courseMap.get(combi) ? courseMap.get(combi) : max;
                }
            }

            for(String combi : courseMap.keySet()){
                if(combi.length() == i){
                    if(courseMap.get(combi) == max) courseList.add(combi);
                }
            }
        }

        return courseList.stream().sorted().toArray(String[]::new);
    }

	// 주문 횟수 조합 생성
    void combination(char[] arr, boolean[] visited, HashMap<String, Integer> courseMap, int start, int menuCnt) {
        if (menuCnt == 0) {
            StringBuilder combinationString = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                if (visited[i]) combinationString.append(arr[i]);
            }

            if(courseMap.containsKey(combinationString.toString())){
                courseMap.put(combinationString.toString(), courseMap.get(combinationString.toString()) + 1);
            } else {
                courseMap.put(combinationString.toString(), 1);
            }

            return;
        }

        for (int i = start; i < arr.length; i++) {
            visited[i] = true;
            combination(arr, visited, courseMap, i + 1, menuCnt - 1);
            visited[i] = false;
        }
    }
}

소감

• 문제 설명이 개똥이다. 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 이걸보고 어떻게 같은 길이의 메뉴중에서 가장 많이 주문이 된 메뉴만 선정하는 건지 이해할 수 있지?
• 이것때문에 두세시간은 더 걸렸다. 결국 사람들이 남긴 힌트보고 풀었지만;
• 조합에 대해서 문제를 풀면서 공부하게 되었다. 꼭 머릿속에 기억하자.