[Level_2 / C++ / 카카오] 메뉴 리뉴얼

<next_permutation> 모든 경우의 수 정렬

---

  1. course 사이즈 만큼 for문 돌리기
  2. 각 손님이 주문한 메뉴가 course 사이즈보다 작으면 continue; 
  3. next_permutation 사용해서 변화되는 인덱스 값들에 해당하는 문자들로 문자열을 만들고 map에 저장 
  4. next_permutation 종료된 후 제일 큰 값을 갖는 key값을 answer에 push_back;
  5. 알파벳 오름차순으로 정렬     

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp (pair<string,int>a,pair<string,int>b){
    return a.second>b.second; 
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0; i<course.size(); i++){
        map <string, int> m; 
        for(int j=0; j<orders.size(); j++){
            string s= orders[j]; 
            if(course[i]>s.size())continue; 
            sort(s.begin(),s.end());             
            vector <bool> check (s.size(),0); 
            for(int k=s.size()-course[i]; k<s.size(); k++) check[k]=1;             
            do{
                string s1 =""; 
                for(int k=0; k<s.size(); k++){
                    if(check[k])s1+=s[k]; 
                }
                m[s1]++; 
            }while(next_permutation(check.begin(),check.end())); 
        }
        if(m.empty())continue;                
        vector <pair<string, int>> v(m.begin(),m.end()); 
        sort(v.begin(),v.end(), cmp); 
        if(v.begin()->second==1)continue; 
        for (auto x : v)cout<< x.first <<" "<<x.second<<endl; 
        int compare = v.begin()->second; 
        for(auto x : v){
            if(x.second==compare)answer.push_back(x.first); 
            else break; 
        }
    }
    sort(answer.begin(),answer.end()); 
    return answer;
}

 

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