프로그래머스 - 메뉴 리뉴얼(2021 KAKAO BLIND RECRUITMENT)

주문한 메뉴(string)에 대해 course 메뉴의 개수만큼(2, 3, 4 ...) substring을 구하여 vector에 저장한 뒤, 가장 많이 주문한 코스 메뉴 조합을 answer에 추가하여 return하면 된다. 

 

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
map<string, int> m;
vector<string> v;
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<int> pick;
    vector<string> answer;
    int c_len = course.size();
    int o_len = orders.size();
    for(int j=0; j<o_len; j++)
        sort(orders[j].begin(), orders[j].end());
    for(int i=0; i<c_len; i++)
    {
        for(int j=0; j<o_len; j++)
        {
            int s_len = orders[j].size();
            if (s_len < course[i])
                continue;
            for(int k=0; k<s_len - course[i]; k++)
                pick.push_back(0);
            for(int k=0; k<course[i]; k++)
                pick.push_back(1);
            do{
                string tmp = "";
                for(int k=0; k<pick.size(); k++)
                    if (pick[k] == 1)
                        tmp += orders[j][k];
                if (!m[tmp])
                    v.push_back(tmp);
                m[tmp]++;
            }while (next_permutation(pick.begin(), pick.end()));
            pick.clear();
        }
        int cnt = -1;
        for(int j=0; j<v.size(); j++)
            cnt = max(cnt, m[v[j]]);
        if (cnt >= 2)
        {
            for(int j=0; j<v.size(); j++)
                if (cnt == m[v[j]])
                    answer.push_back(v[j]);
        }
        v.clear();
        m.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}

map과 next_permutation을 이용하여 해결했다.