[c++][프로그래머스] 메뉴 리뉴얼

프로그래머스 메뉴 리뉴얼 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72411

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

문제 풀이

• 이 문제는 조합(combination)을 활용하여 해결하는 문제입니다. 일반적으로 조합을 구하는 방법은 DFS를 활용하여 재귀적으로 구하는 방법과 next_permutation, prev_permutation을 활용하여 반복문으로 구하는 방법이 있는데, 저는 next_permutation을 사용해 구현했습니다. 
• 각 order별로 course 길이의 조합을 구해 map에 저장하고 그 중 가장 많이 주문된 조합을 answer vector에 담아줍니다. 

코드

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

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // order 미리 정렬해두기
    for(string &order: orders) sort(order.begin(), order.end());
    for(auto c: course) {
        map<string, int> m;
        for(auto order: orders) {
            if(order.length() > c) {
                vector<bool> comb(order.length()-c, false);
                for(int i=0; i<c; ++i) comb.push_back(true);
                
                // do-while & next_permutation으로 조합 구하기
                do {
                    string temp = "";
                    for(int i=0; i<order.length(); ++i) {
                        if(comb[i]) temp += order[i];
                    }
                    
                    m[temp]++;
                } while(next_permutation(comb.begin(), comb.end()));
            }
            else if(order.length() == c) m[order]++;
        }
        
        // 가장 많이 주문된 조합 찾기
        int max_val = max_element(m.begin(), m.end(), 
                                   [] (const pair<string, int> &a, const pair<string, int> &b) {
                                       return a.second < b.second;
                                   })->second;
        if(max_val < 2) continue;
        for(auto iter: m) {
            if(iter.second == max_val) {
                answer.push_back(iter.first);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

실행 결과