Level 2. 메뉴 리뉴얼

Level 2. 메뉴 리뉴얼

 

 

코드가 다소 길긴 하지만 엄청 복잡하지는 않다.

1. 모든 메뉴에서 가능한 n개 메뉴의 경우의 수를 구한다.
2. 그 중 2번 이상 주문된 조합을 주문 수를 기준으로 메뉴 vector를 저장하는 set에 넣는다.
3. 마지막에 가장 많게 주문된 조합들을 정답에 넣는다.

 

경우의 수 조합을 구할 때, 알파벳이 들어있는 map을 사용하므로 별도의 정렬은 필요하지 않다.

 

하지만, 모든 메뉴를 map에 넣어 가능한 경우의 수를 계산해서 그런지 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

vector<string> get_combinations(map<char, bool>& mp, int start, int n)
{
    if (n == 0)
        return { "" };

    vector<string> result;

    for (int i = start; i <= mp.size() - n; ++i)
    {
        char c = next(mp.begin(), i)->first;

        for (string sub : get_combinations(mp, i + 1, n - 1))
            result.emplace_back(string(1, c) + sub);
    }

    return result;
}

bool belongs(string& A, string& B)
{
    unordered_map<char, bool> umapB;

    for (char c : B)
        umapB[c] = true;

    for (char c : A)
        if (!umapB[c]) return false;

    return true;
}

vector<string> solution(vector<string> orders, vector<int> course)
{
    set<string> answer;
    map<char, bool> mp;

    for (string& order : orders)
        for (char c : order)
            mp[c] = true;

    for (int n : course)
    {
        map<int, vector<string>> menus;

        for (string comb : get_combinations(mp, 0, n))
        {
            int nBelongs = 0;

            for (string& order : orders)
                nBelongs += belongs(comb, order);

            if (2 <= nBelongs)
                menus[nBelongs].emplace_back(comb);
        }

        if (0 < menus.size())
            for (string& menu : menus.rbegin()->second)
                answer.emplace(menu);
    }

    return vector<string>(answer.begin(), answer.end());
}

 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

void combination(map<string, int>& mp, string src, string crs, int depth)
{
    if (crs.length() == depth)
    {
        ++mp[crs];

        return;
    }

    for (int i = 0; i < src.length(); ++i)
        combination(mp, src.substr(i + 1), crs + src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course)
{
    set<string> answer;

    for (string& order : orders)
        sort(order.begin(), order.end());

    for (int crs : course)
    {
        int sup = 0;
        map<string, int> mp;

        for (string order : orders)
            combination(mp, order, "", crs);

        for (auto it : mp)
            sup = max(sup, it.second);

        for (auto it : mp)
            if (2 <= sup && it.second == sup)
                answer.emplace(it.first);
    }

    return vector<string>(answer.begin(), answer.end());
}