[Programmers] 메뉴 리뉴얼

손님들이 시킨 메뉴들을 잘 구성하여 세트메뉴를 만드는 문제이다.

손님들이 가장 많이 시킨 것을 원하는 세트메뉴의 구성 단품 개수에 맞게 골라서 세트메뉴로 만들고자 한다.

문제 해결 전략
우선 각 손님이 먹은 메뉴들을 원하는 갯수의 조합으로 모든 경우를 생각해 봐야 한다.

예를들어 "ABCD"를 먹은 손님이 있다고 하고, 세트메뉴 구성 단품의 갯수를 2개로 하고 싶어 한다면 AB, AC, AD, BC, BD, CD를 모두 구해야 한다.

그리고 이 과정을 모든 손님들에 대하여 모든 원하는 개수 만큼 반복해야 한다.

우선 음식 순서를 오름차순으로 sort 해 준다.

그리고 나서 모든 조합을 구하기 위해 prev_permutation을 활용하였다.

구해진 문자열을 map에 저장하는데, 만약 이미 존재한다면 map의 value 값을 ++ 해 주고, 없다면 insert 해 준다.

단품 갯수에 따라 진행을 해 주는데, 각 진행마다 map에 저장된 value 값중 가장 큰 값에 해당하는 key 값을 answer에 넣어 준다.

이 과정을 모든 원하는 갯수에 따라 진행한 후 answer역시 sort해 준다.

코드

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

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i=0;i<course.size();i++){
        int n = course[i];
        map<string, int> m;
        for(int j=0;j<orders.size();j++){
            sort(orders[j].begin(), orders[j].end());
            vector<int> tmp;
            if(orders[j].size() < n)
                continue;
            for(int k=0;k<orders[j].size();k++){
                if(k<n)
                    tmp.push_back(1);
                else
                    tmp.push_back(0);
            }
            do{
                string str = "";
                for(int k=0;k<orders[j].size();k++){
                    if(tmp[k] == 1)
                        str += orders[j][k];
                }
                if(m.find(str) != m.end())
                    m[str]++;
                else
                    m.insert(make_pair(str,1));
            }while(prev_permutation(tmp.begin(), tmp.end()));
        }
        int mx = 1;
        string ms;
        for(auto it = m.begin();it != m.end();it++){
            if(it->second > mx){
                mx = it->second;
            }
        }
        if(mx == 1)
            continue;
        for(auto it = m.begin();it != m.end();it++){
            if(it->second == mx){
                answer.push_back(it->first);
            }
        }
        m.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/72411