質問元:[Programmers]メニューの更新、https://programmers.co.kr/learn/courses/30/lessons/72411

👨‍🏫質問する

レストランを運営する스카피は、コロナ19による不況を克服するため、メニューの再設計を検討している.
以前は単品しか提供していなかったメニューを組み合わせて、セットで再組み合わせして、新しいメニューを提供することにしました.どの単品メニューを組み合わせてセットメニューを構成するかを考えた「scapi」は、以前のお客様一人一人が注文したときに一番多かった単品メニューをセットメニューにすることにしました.
しかし、少なくとも2つの単品メニューが選択できることを望んでいます.また、少なくとも2名以上のお客様からご注文いただいた単品メニューの組み合わせについては、コースメニューの候補リストにのみ入れることにしました.
例えば、6名様からご注文いただいた単品メニューの組み合わせは以下の通りです.
(お客様1人につき2つ以上の単品メニューを注文しなければなりません.各単品メニューはアルファベットA~Zで表示されます)
お客様番号注文の単品メニューセット1番お客様A、B、C、F、G 2番お客様A、C 3番お客様C、D、E 4番お客様A、C、D、E 5番お客様B、C、F、G 6番お客様A、C、D、E、H
最も頻繁に注文される単品メニューの組み合わせに基づいて、skapiは次のコースメニュー構成候補オプションを作成します.
コースメニュー構成説明料理2コースA、C 1番、2番、4番、6番のお客様は全部で4番を注文しました.3品の料理C、D、E 3番、4番、6番のお客様は全部で3品の料理を注文しました.4品B、C、F、G 1、5番のお客様は全部で2品注文しました.4品A C D E 4番6番のお客様は全部で2番をご予約いただいております
各ゲストが注文した単品メニューが文字列形式で含まれる並び順、추가하고 싶어하는料理を含む単品メニュー数の並び順をパラメータとする場合は、「scapi」が新しく追加した料理のメニュー構成を文字列形式で並びに含めて返すソリューション関数を完了します.
せいげんじょうけん

Orders配列のサイズは2個または20個を超えない。 Orders配列の各要素は、2または10未満のサイズの文字列です。 各文字列は、大文字のみで構成されます。 各文字列には同じ文字が重複していません。 course配列のサイズは10を超えない。 course配列の各要素の自然数は、2以下の昇順に並べられます。 course配列には重複する値はありません。 正解は、各メニューの構成を文字列で並べ、辞書順に昇順に並べて返すことです。 アレイ内の各要素に格納されている文字列も、アルファベット昇順に並べなければなりません。 注文が最も多いメニュー構成の場合は、すべて箱詰めして返します。 Ordersおよびcourseパラメータは、返される配列の長さが少なくとも1であることを指定します。

サンプルI/O

orderscourseresult["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"][2,3,4]["AC", "ACDE", "BCFG", "CDE"]["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"][2,3,5]["ACD", "AD", "ADE", "CD", "XYZ"]["XYZ", "XWY", "WXA"][2,3,4]["WX", "XY"]

I/O例説明

I/O例#1
問題の例.
I/O例#2
ADを3回、CDを3回、ACDを2回、ADEを2回、XYZを2回注文しました.
1人が5品を注文したが、少なくとも2人以上が1品を注文したため、新しい5品は追加されない.
I/O例#3
WX 2回とXY 2回注文しました.
3名様とも単品メニューを3つご注文いただいておりますが、少なくとも2名様以上のお客様がご注文いただいた料理はセット後のみとなっておりますので、3品のセットは追加されません.
また、4つ以上の単品メニューを注文したお客様がいないため、4つの料理からなるコースを新たに追加することもありません.

💻コード#コード#

import java.lang.StringBuilder;
import java.util.*;
import java.util.Map.Entry;

class Solution {

    // 전역 변수 map
    static HashMap<String, Integer> map;
    
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> aList = new ArrayList<>();
        map = new HashMap<>();
        
        /*
         * order 배열의 각 요소를 꺼내 문자 배열로 쪼갠 뒤, course의 각 요소를
         * 조합 함수의 target으로 전달하여 조합 함수 호출.
         */
        for(int i = 0; i < orders.length; i++){
            char[] c = orders[i].toCharArray();
            StringBuilder sb = new StringBuilder();
            Arrays.sort(c);
            
            for(int j = 0; j < course.length; j++){
                combination(c, sb, 0, 0, course[j]);
            }
        }
        
        // map 정렬을 위한 EntrySet
        List<Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
        
        // EntrySet의 value, 즉 해당 조합이 나온 횟수를 기준으로 내림차순 정렬
        Collections.sort(list, new Comparator<Entry<String, Integer>>(){
            @Override
            public int compare(Entry<String, Integer> m1, Entry<String, Integer> m2){
                return m2.getValue() - m1.getValue();
            }
        });
        
        /* 
         * 가장 인기있는 조합의 메뉴를 요리 가짓수 별로 추가하고, 
         * 만약 같은 요리 가짓수에 인기 순위도 같을경우 모두 추가
         */
        for(int i = 0; i < course.length; i++){
            int max = 0;
            
            for(Entry<String, Integer> entry : list){
                String key = entry.getKey();
                int value = entry.getValue();

                if(course[i] == key.length() && value >= 2){
                    if(value >= max){
                        aList.add(key);
                        max = value;
                    }
                }
            }
        }
        
        // 새로 추가하게될 메뉴들을 오름차순으로 정렬
        Collections.sort(aList);
        
        String[] answer = new String[aList.size()];
        
        for(int i = 0; i < aList.size(); i++){
            answer[i] = aList.get(i);
        }
        
        return answer;
    }
    
    // character 배열 c의 조합을 만들어주는 함수
    public static void combination(char[] c, StringBuilder sb, int index, int depth, int target){
    
        // 재귀 깊이와 target이 같아지면 map에 해당 조합을 추가, 이미 있는 메뉴일 경우 기존 value에 +1을 해준다.
        if(depth == target){
            map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
            return;
        }
        
        for(int i = index; i < c.length; i++){
            sb.append(c[i]);
            combination(c, sb, i + 1, depth + 1, target);
            sb.delete(depth, depth + 1);
        }
    }
}

💡ポスト

再帰関数は使いたくないので、通常はDFSをstackの繰り返し文として実現していますが、シーケンスは実現していますが、組み合わせを実現するのに時間がかかりすぎて、諦めて再帰で解決しました…😑
また,組合せアルゴリズムを探して問題を解決すると,PythonとC++はライブラリを用いてシーケンスと組合せ関数を提供し,初めてJavaを嫌うことが分かった.😭😂😭
しかし、ソートと組み合わせアルゴリズムを直接実現する機会もあり、普段使いたくない再帰関数を利用して問題を解くことは、新鮮で役に立つ良い問題だと思います.😊