[프로그래머스 level2] 메뉴 리뉴얼 (C++)

조합과 map을 사용해서 해결할 수 있는 문제이다. (프로그래머스 level2)

문제는 다음과 같다.
메뉴 리뉴얼

어떻게 풀었는가?

1. next_permutation()으로 조합구함
2. map에 해당 문자열을 추가하고 문자열 등장 횟수 확인
3. 가장 많이 나온 문자열을 출력

조건

1. 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다.
2. 2명 이상의 코스요리가 없을 경우에는 해당 개수의 코스요리는 출력하지 않는다.
3. 가장 많이 주문된 메뉴 구성이 여러개라면, 모두 배열에 담아 return 한다.
4. 오름차순으로 정렬해서 return 한다.

구현

1. 해당 손님이 시킨 단품메뉴의 개수만큼 vector를 할당한다. (len)
2. 구해야하는 코스요리의 개수(cnt)만큼 vector에 true를 할당한다.
3. 이 vector에 대해서 next_permutation을 반복한다. -> 조합구하기
4. 조합을 구해 true인 문자를 모아 문자열로 만들고 map 사용
   • 이미 있는 문자열 -> m[tmp]++;
   • 없는 문자열 -> m.insert({tmp,1});
5. 가장 많이 나온 문자열을 answer에 추가한다.

1~5 반복하면됨

코드

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

using namespace std;
map <string,int> m;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0; i<course.size(); i++)
    {
        int cnt = course[i];
        for(int j=0; j<orders.size(); j++)
        {
            int len = orders[j].length();
            if(len < cnt) continue;
            sort(orders[j].begin(), orders[j].end());
            vector <bool> v(len-cnt, false);
            v.insert(v.end(), cnt, true);
            
            do{
                string tmp = "";
                for(int k=0; k<len; k++)
                {
                    if(v[k]){
                        tmp += orders[j][k];
                    }
                }
                if(m.find(tmp) == m.end()){
                    m.insert({tmp,1});
                }
                else{
                    m[tmp]++;
                }
            }while(next_permutation(v.begin(), v.end()));
        }
        int maxCnt = 0;
        for(auto itr=m.begin(); itr!=m.end(); itr++)
        {
            if(maxCnt < itr->second) maxCnt = itr->second;
        }
        if(maxCnt==1) continue;
        for(auto itr=m.begin(); itr!=m.end(); itr++)
        {
            if(maxCnt == itr->second)
            {
                answer.push_back(itr->first);
            }
        }
        m.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}