메뉴 리뉴얼 /조합 익히자

벡터 맵에 각 조합을 저장한다.

//nCr(orders[j].size() C course[i]).

 

그러나, 조합 생성을 못하겠어서 제미나이에게 물어봤다.

 

이러면 모든 조합과 그 갯수가 나온다.

이제 값 기준 내림차순 하여 제일큰값과 같은 값인 코스들을 answer에 추가해주면 된다.

 

시간 초과가 안날진 모르겠지만.. 제출하지 않고 끝내겠다.

내가 풀지도 못했고, 재귀 조합을 사용할 줄도 모르겠다.

다시.. 돌아오자.

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

using namespace std;

//코스요리: 2가지 이산의 단품 조합, 2인 이상의 손님
//단품: 26가지 A~Z
//2개코스가 무조건 3개코스에 속하지 않는다.

//결과: 코스 오름차순, 주문수 같다면 함께.
//코스요리 조건에 해당하지 않는다면 추가하지 않음.


void generateCombinations(const string& letters, unordered_map<string, int>& combinationCounts, string current, int index, int count, int k) 
{
    if (count == k) {
        combinationCounts[current]++; 
        return;
    }

    for (int i = index; i < letters.size(); ++i) {
        generateCombinations(letters, combinationCounts, current + letters[i], i + 1, count + 1, k);
    }
}

void getCombinationCounts(const string& letters, int k, unordered_map<string, int>& combinationCounts) { // 변경됨
    generateCombinations(letters, combinationCounts, "", 0, 0, k);
}


vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    int courseMax = course.size() - 1;
    vector<unordered_map<string, int>> courseMap(course.size()); //course만큼 각 order조합의 map.

    //nCr(orders[j].size() C course[i])

    //map 조합을 위한 정렬
    for (int i = 0; i < orders.size(); ++i)
    {
        sort(orders[i].begin(), orders[i].end());
    }


    for (int i = 0; i < course.size(); ++i)
    {
        for (int j = 0; j < orders.size(); ++j)
        {
            if (course[i] > orders[j].size())
                continue;

            getCombinationCounts(orders[j], course[i], courseMap[i]);

        }
    }
   

    
        //count 높은순 내림차순, 높은 것, 동점은 함께 answer 추가.

    return answer;
}

 

 

바로 돌아왔다.

제미나이한테 물어보고 익숙한 코드로 함.

 

조합 익숙해져야 한다.

c++ 20부터는 순열로 우회하지 않고, 바로 조합을 만들 수 있다고한다.

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

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    vector<unordered_map<string, int>> courseMap(course.size()); //course만큼 각 order조합의 map.

    //nCr(orders[j].size() C course[i])

    for (int i = 0; i < orders.size(); ++i)
    {
        //map 조합을 위한 정렬
        sort(orders[i].begin(), orders[i].end());

        vector<bool> isSelect(orders[i].size(), false);

        for (int j = 0; j < course.size(); ++j)
        {
            if (course[j] > orders[i].size())
                break;

            for (int k = 0; k < course[j]; ++k)
            {
                isSelect[k] = true;
            }

            do
            {
                string combi = "";
                for (int l = 0; l < orders[i].size(); ++l)
                {
                    if (isSelect[l])
                        combi += orders[i][l];
                }

                courseMap[j][combi]++;
            } while (prev_permutation(isSelect.begin(), isSelect.end()));
        }
    }
   
    //count 높은순 내림차순, 높은 것, 동점은 함께 answer 추가.
    for (int i = 0; i < courseMap.size(); ++i)
    {
        vector<pair<string, int>> vec(courseMap[i].begin(), courseMap[i].end());
        sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {return a.second > b.second; });
        int max = vec[0].second;
        if (max < 2)
            break;

        for (int j = 0; j < vec.size(); ++j)
        {
            if (max > vec[j].second)
                break;
            answer.push_back(vec[j].first);
        }
    }   

    sort(answer.begin(), answer.end());

    return answer;
}