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

문제 출처:

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

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

 

조합, map을 이용해서 풀이할 수 있다.

코스요리를 이루는 메뉴의 개수가 곧 조합으로 뽑아야 할 개수에 해당하기 때문에, 뽑아주고, 2명이상의 사람에게 가장 많이 뽑힌 메뉴들을 개수별로 벡터에 저장하고, 오름차순으로 사전순 정렬을 해주면 된다.

 

 

 

#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
vector<string> solution(vector<string> ord, vector<int> crs) {
    vector<string> ans;
    for(int i = 0 ; i < crs.size() ; i++){
        int cnt = crs[i];
        for(int j = 0 ; j < ord.size() ; j++){
            
            string curOrd = ord[j];
            sort(curOrd.begin(), curOrd.end());
            if(curOrd.length() < cnt) continue;
            
            vector<int> tmp;
            for(int k = 0 ; k < cnt ; k++){
                tmp.push_back(0);
            }
            for(int k = cnt ; k < curOrd.length() ; k++){
                tmp.push_back(1);
            }
            
            do{
                string str ="";
                for(int k = 0 ; k < curOrd.size() ; k++){
                   
                    if(tmp[k] == 0){
                        str += curOrd[k];
                    }
                }
                if(mp.find(str) == mp.end()){
                    // map에 없으면
                    mp.insert({str, 1});
                }
                else{
                    mp[str]++;
                }
            }while(next_permutation(tmp.begin(), tmp.end()));
        }
        // cur개의 메뉴를 뽑을때, 최대 빈도수로 등장한 메뉴조합
        int maxCnt = 1;
        
        for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
            // cout << itr->first << " = " << itr->second << '\n';
            if(itr->second > maxCnt){
                maxCnt = itr->second;
            }
        }
        if(maxCnt == 1) continue;
        for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
            if(itr->second == maxCnt){
                ans.push_back(itr->first);
            }
        }
        mp.clear();
    }
    
    sort(ans.begin(), ans.end());
    return ans;
}