프로그래머스-메뉴리뉴얼

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

 

<풀이>

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool cmp(pair<string, int>a, pair<string, int> b){
    return a.second > b.second;
}


void DFS(map<string, int>& dic, string& order, string tmp, int index, int depth){
    if(depth == tmp.length()){
        dic[tmp]++;
        return;
    }

    for(int i = index; i<order.length(); i++){
        tmp[depth] = order[i];
        DFS(dic,order,tmp,i+1,depth+1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    map<string, int> dic;
    
    for(int i=0; i<orders.size(); i++){
        sort(orders[i].begin(), orders[i].end());
        for(int j=0; j<course.size(); j++){
            string tmp = "";
            tmp.resize(course[j]);
            DFS(dic,orders[i], tmp,0,0);
        }
    }
   
    vector<pair<string,int>> sorted;
    
    for(auto& order : dic)//dic에서 차례대로 객체를 꺼내서 order에 넣는다
        if(order.second > 1)
            sorted.push_back({order.first,order.second});
    
    sort(sorted.begin(), sorted.end(),cmp);
    
    for(int i=0; i<course.size(); i++){
        int max = 0;
        for(int j=0; j<sorted.size(); j++){
            if(sorted[j].first.length() != course[i])
                continue;
            else if(max == 0){
                answer.push_back(sorted[j].first);
                max = sorted[j].second;
            }
            else if (max == sorted[j].second)
                answer.push_back(sorted[j].first);
            else
                break;
        }
    
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

 

-참고한 사이트

https://ansohxxn.github.io/programmers/82/