Programmers - 메뉴 리뉴얼 with JAVA

 

문제

여러명의 손님들이 각자 주문했던 음식 리스트가 있다. 이를 활용해 최소 2명의 손님이 주문한 2개이상의 음식세트를 만들려고 한다.

이 때, 음식세트의 주문수가 최대인것들을 정렬해서 출력하라.

 

 

 

로직

 

1. 각 주문마다 course에 맞는 조합 맵 구하기 : map , 조합마다 글자 길이에 맞는 최대값 갱신 : maxCount

2. 조합의 길이마다 최대값이 2보다 같거나 크면서 맵의 값(주문 된 횟수)이 최대값인 경우 결과에 반영 : answer

3. answer 정렬

 

예를 들어, [1, 2, 3, 4, 5]가 있다고 가정할 때 (각 번호는 음식 번호를 의미)

음식의 종류 3개로 만들 수 있는 조합은

[1, 2, 3]

[1, 2, 4]

[1, 2, 5]

[1, 3, 4]

 

이런식으로 나갈 것이다. 이러한 경우에는 매번 경우의 수마다 인덱스를 보내줘야함을 기억하자.

 

 

 

코드

import java.util.*;
class Solution {
    public static HashSet<String> check = new HashSet<>();
    public List<String> solution(String[] orders, int[] course) {
        HashMap<String, Integer> map = new HashMap<>();
        int[] maxCount = new int[21];
        for(String order : orders){
            for(int count : course){
                char[] menu = order.toCharArray();
                find(menu,count,0,new ArrayList<>(),new boolean[menu.length]);
                for(String now : check){
                    map.put(now, map.getOrDefault(now, 0)+1);
                    maxCount[count] = Math.max(maxCount[count], map.get(now));
                }
                check = new HashSet<>();
            }
        }
        List<String> answer = new ArrayList<>();
        for(String key : map.keySet()){
            int length = key.length();
            if(maxCount[length] < 2){
                continue;
            }
            if(map.get(key) == maxCount[length]){
                answer.add(key);
            }
        }
        Collections.sort(answer);
        return answer;
    }
    public static void find(char[] menu, int count, int start,
                            List<Character> result, boolean[] visited){
        if(count == result.size()){
            Collections.sort(result);
            StringBuilder sb = new StringBuilder();
            for(char now : result){
                sb.append(now);
            }
            check.add(sb.toString());
            return;
        }
        for(int i=start; i<menu.length; i++){
            if(!visited[i]){
                visited[i] = true;
                result.add(menu[i]);
                find(menu, count, i+1, result, visited);
                result.remove(Character.valueOf(menu[i]));   
                visited[i] = false;
            }
        }
    }
}