메뉴 리뉴얼(41분)

https://school.programmers.co.kr/learn/courses/30/lessons/72411

구현 아이디어 5분 구현 36분

풀이

DFS 안의 if (L == e) 구문에서 좀 헤멨다. 해당 코스요리가 2번 이상 주문되면 일단 answer에 넣는줄 알았는데 최대 주문 코스요리를 골라 answer에 넣어야했다.

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

using namespace std;

int check[26], max_order = 2;
char comb[10];
vector<char> for_course;
vector<string> result, answer;

void DFS(int L, int i, int e, const vector<string>& orders)
{
    if (L == e)
    {
        // 코스요리에 적합한지 확인하고 answer에 push.
        int sum = 0;
        for (int i = 0; i < orders.size(); ++i)
        {
            bool flag = false;
            for (int j = 0; j < e; ++j)
            {
                for (int k = 0; k < orders[i].length(); ++k)
                {
                    if (comb[j] == orders[i][k])
                    {
                        flag = true;
                        break;
                    }
                    else flag = false;
                }
                // orders[i]를 전부 돌았지만 flag가 false.
                // i번째 주문자는 이 코스요리를 구매하지 않는다는 뜻.
                if (!flag) break;
            }
            if (flag) ++sum;
        }

        if (sum < max_order) return;

        string tmp;
        for (int i = 0; i < e; ++i)
            tmp += comb[i];

        if (sum > max_order)
        {
            max_order = sum;
            result.clear();
        }

        result.push_back(tmp);
    }
    else
    {
        for (; i < for_course.size(); ++i)
        {
            comb[L] = for_course[i];
            DFS(L + 1, i + 1, e, orders);
        }
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    int N = orders.size();

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < orders[i].length(); ++j)
            check[orders[i][j] - 'A'] += 1;

    for (int i = 0; i < 26; ++i)
        if (check[i] >= 2) for_course.push_back(i + 'A');

    int M = course.size();
    for (int i = 0; i < M; ++i)
    {
        result.clear();
        max_order = 2;

        // 레벨, 코스 개수, 주문 정보.
        DFS(0, 0, course[i], orders);

        for (auto& it : result)
            answer.push_back(it);
    }

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

    return answer;
}