[프로그래머스] 메뉴 리뉴얼 문제풀이 c++

DFS와 map을 이용한 문제이다.

전체에서 course의 개수만큼 뽑는 모든 경우의 수를 탐색한다.(조합,dfs)

map으로 각 조합이 가능한 경우의 수를 저장하고,

max_order로 가장 많이 주문된 코스를 구한다.

최소주문횟수는 2회이므로 max_order>1일경우에만 

map 탐색을 통해 max_order인 코스를 구하여

answer에 push한다.

정렬된 결과를 출력해야하므로 answer을 마지막에 sort한다.

 

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

using namespace std;

map<string, int> m;
int max_order = -1;

void DFS(string order, string list, int depth){
    if(list.size() == depth){
        int tmp = ++m[list];
        max_order = max(max_order,tmp);
    }   
    else{
        for(int i=0; i<order.size(); i++){
            DFS(order.substr(i+1), list+order[i], depth);
        }
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(auto &order:orders){
        sort(order.begin(),order.end());
    }
    for(int c:course){
        max_order = -1;
        for(auto &order:orders){
            if(order.size()>=c)
                DFS(order,"",c);
        }
        if(max_order>1){
            for(auto it = m.begin(); it!= m.end(); it++){
                if(it->second == max_order){
                    answer.push_back(it->first);
                }    
            }
        }
         m.clear();
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}