[アルゴリズム解答解析]プログラマ2021 KAO BLIND RECRUITMENTメニュー更新

今日の質問はメニューの更新です.白俊はだんだん飽きてきて、久しぶりにプログラマーのところを探しました!
実は昨日からだったのですが、、、どうせそうなんです^^、
カカオ豆はあと2週間くらいしか残っていないので、今週からカカオ豆の問題を重点的に解決します.結局Kakao試験は長くて2回も難易度があった.

2021 KAKAO BLIND RECRUITMENTメニュー更新

レストランを経営するスカフィーは、コロナ19による不況を克服するため、メニューの再設計を検討している.
以前は単品しか提供していなかったメニューを組み合わせて、セットで再組み合わせして、新しいメニューを提供することにしました.どの単品メニューを組み合わせてセットメニューを構成するかを考えた「scapi」は、以前のお客様一人一人が注文したときに一番多かった単品メニューをセットメニューにすることにしました.
しかし、少なくとも2つの単品メニューが選択できることを望んでいます.また、少なくとも2名以上のお客様からご注文いただいた単品メニューの組み合わせについては、コースメニューの候補リストにのみ入れることにしました.
各顧客が注文した単品メニューが文字列形式でリストされた並べ替え注文と、「Scapi」が追加したいセットを構成する単品メニューの数の並べ替えcourseをパラメータとする場合.ソリューション関数を完了し、「scapi」を新しく追加したコースのメニュー構成を文字列で並べて返してください.

にゅうしゅつりょく

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つの料理からなるコースを新たに追加することもありません.

私の答え

特に使われていないアルゴリズムやアイデア!色々な条件をよく考えて実施すべきImplementation問題で、しかも漏れのない条件で、丁寧に実施すべきだと思います!
入力された注文の種類と出力のルートから見ると、26種類のメニューが独立しています.したがって、入力した各注文では、まず各メニューについて可能な組み合わせを見つけなければなりません.たとえば、「ABC」と入力した場合、この場合可能な組み合わせは「AB」、「AC」および「BC」である.
また、第3例I/Oでは、「XWY」、「WXA」と入力されているが、出力には「WX」のみが存在しており、各メニューの順序が関係していないことを示している.
求められた各組合せの配列combinationsの各組合せをカウントする.この過程でorders.size() * 27サイズの2次元配列orderCheckを使用し、orderCheckに注文したメニューがあります.例えば、order[i]が「AB」である場合、orderCheck[i][1]、orderCheck[i][2]はtrueである.
各組み合わせに従って、全てのメニューから数回注文した後、combinations[i].secondに保存する.また、この過程で、1品あたりの長さが最も多く注文された組み合わせは何回ありますか.
その後、2番目の値が完成したcombinationsのうち、各料理の長さに応じて、最も多いメニューの組み合わせをanswerに入れればよい.

コード#コード#

#include <string>
#include <vector>
#include <algorithm>

// 프로그래머스 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼, level 2
using namespace std;

bool byLength(string a, string b){
    if (a.size() != b.size()){
        return a.size() < b.size();
    }
    return a<b;
}

bool byPairLength(pair<string, int> a, pair<string, int> b){
    if (a.first.size() != b.first.size()){
        return a.first.size() < b.first.size();
    }
    return a.first<b.first;
}

bool byLenghtAndCount(pair<string, int> a, pair<string, int> b) {
    if (a.first.size() == b.first.size()){
        return a.second > b.second;
    }else{
        return a.first.size() < b.first.size();
    }
}


// alphabets 에서 r개를 뽑는 조 구하기 
void getCombination(vector<char> alphaets, int r, vector<pair<string, int>> & combinations){
    int n = alphaets.size();

    vector<bool> select(n-r, false);
    for (int i = 0; i < r; ++i) {
        select.push_back(true);
    }

    do{
        string combi = "";
        for (int i = 0; i < n; ++i) {
            if (select[i]){
                combi += alphaets[i];
            }
        }
        combinations.push_back(make_pair(combi, 0));
    }while (next_permutation(select.begin(), select.end()));
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    sort(orders.begin(), orders.end(), byLength);
    
    // 가능한 조합과 그 조합의 주문 횟수 저장 배열 
    vector<pair<string, int>> combinations;  
    
    // 각 주문별로 주문된 메뉴 체크 배열 
    vector<vector<bool>> orderCheck(orders.size(), vector<bool>(27, false));

    for (int i = 0; i < orders.size(); ++i) {
        vector<char> alphabets;
        
        // 주문별로 주문된 메뉴 내에서 가능한 조합 구하기 
        for (int j = 0; j < orders[i].size(); ++j) {
            alphabets.push_back(orders[i][j]);
            orderCheck[i][orders[i][j]-64] = true;
        }
        sort(alphabets.begin(), alphabets.end());

        for (int j = 0; j < course.size(); ++j) {
            if (course[j] <= orders[i].size()){
                getCombination(alphabets, course[j], combinations);
            }
            else break;
        }
    }

    // 조합에서 중복 제거
    sort(combinations.begin(), combinations.end(), byPairLength);
    combinations.erase(unique(combinations.begin(), combinations.end()), combinations.end());

    int maxLen = course[course.size()-1];
    vector<int> maxCount(maxLen+1, -1);

    for (int i = 0; i < combinations.size(); ++i) {
        int count = 0;
        int courseLen = combinations[i].first.size();

        // 각 조합 * 각 주문 별로 해당 조합이 주문되었는지를 count 
        for (int j = 0; j < orders.size(); ++j) {
            if(courseLen <=  orders[j].size()){
                bool same = true;
                for (int k = 0; k < courseLen; ++k) {
                    if (!orderCheck[j][combinations[i].first[k]-64]){
                        same = false;
                        break;
                    }
                }
                if (same) count++;
            }
        }
        combinations[i].second = count;
        
        // 2번 이상 주문된 경우 최대 주문 횟수 저장 
        if(count >= 2 && count > maxCount[courseLen]) maxCount[courseLen] = count;
    }

    sort(combinations.begin(), combinations.end(), byLenghtAndCount);


    // 각 조합 길이별로 최대 주문 조합 저장하기 
    for (int i = 0; i < combinations.size(); ++i) {
        int len = combinations[i].first.size();
        if (combinations[i].second == maxCount[len]){
            answer.push_back(combinations[i].first);
        }
    }
    sort(answer.begin(), answer.end());

    return answer;
}