[프로그래머스] 메뉴 리뉴얼(C++)

[문제]

 

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

코딩테스트 연습 - 메뉴 리뉴얼

[풀이]

 

우선 존재하는 모든 메뉴를 c라는 벡터에 insert 해준다.

결과값은 각 알파벳을 기준으로 오름차순으로 정렬되어 있어야 하므로 c를 오름차순으로 정렬해준다.

그 다음으로 course의 케이스마다 만들 수 있는 모든 메뉴 조합을 DFS 함수를 통해서 구한다.

course  배열의 각 개수를 만족하면 각 손님이 해당 메뉴 조합을 시킨 횟수를 count하고 가장 많이 시킨 메뉴 조합을 result를 위한 벡터인 v에 insert한다.

이러한 방식으로 각 course 케이스에 대한 메뉴 조합을 구하고, 가장 많이 시킨 순서대로 정렬하여 return 하면 된다 .

 

[코드]

 

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

using namespace std;

vector<string> order;
vector<char> c;
vector <pair<int , string>> v;
vector <int> comb;
int num=0;

bool comp(const pair<int,string> a, const pair<int,string> b)
{
    if(a.first>b.first) return true;
    else return false;
}

int solve()
{
    int cnt =0;
    for(int i=0;i<order.size();i++){
        bool bCheck = true;
        for(int j=0;j<comb.size();j++){
            if(order[i].find(comb[j]) == -1){
                bCheck= false;
                break;
            }
        }
        if(bCheck)  cnt++;
    }
    return cnt;
}
void DFS(int cnt,int idx)
{
    if(num == cnt)   {
        int res = solve();
        string tmp = "";
        for(int i =0 ;i<comb.size();i++)
            tmp+=comb[i];
        v.push_back({res, tmp});
        return ;
    }
    for(int i=idx;i<c.size();i++){
        comb.push_back(c[i]);
        DFS(cnt+1,i+1);
        comb.pop_back();
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    order = orders;
    
    for(int i=0;i<orders.size();i++){
        for(int j=0;j<orders[i].size();j++){
            if(find(c.begin(),c.end(),orders[i][j]) == c.end()) c.push_back(orders[i][j]);
        }
    
    }
    sort(c.begin(),c.end());
    for(int i=0;i<course.size();i++){
        num = course[i];
        DFS(0,0);
        comb.clear();
        sort(v.begin(),v.end(),comp);
        int res = v[0].first;
        if(res < 2 ) {
            v.clear();
            break;
        }  
        for(int j=0;j<v.size();j++){
            if(v[j].first == res)   answer.push_back(v[j].second);
            else break;
        }
        v.clear();
    }
    sort(answer.begin(),answer.end());
    return answer;
}