[프로그래머스] 2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼 (C++)

문제 링크 : 메뉴 리뉴얼

[문제 접근]

딱 보자마자 조합이 떠올랐던 문제이다.

• 각 orders는 미리 정렬하여 순서에 상관없게 만든다.
  • ex) XY, YX는 같은 조합으로 판단하기 때문에 미리 정렬하여 XY, XY로 만든다.
• 조합 함수를 만들어서 course의 개수에 맞는 메뉴들을 map에 넣는다.
• map을 탐색하면서 가장 인기있는 메뉴를 고른다.
  • 이 때, 가장 인기있는 메뉴가 여러 개면 전부 answer에 넣어준다.
• 마지막으로 answer를 정렬한다.

[소스 코드]

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

void check(string s, string temp, map<string, int> &m, int index, int cnt, int start) {
    if(index==cnt) {
        m[temp]++;
        return;
    }
    for(int i=start ; i<s.size() ; i++) {
        check(s, temp+s[i], m, index, cnt+1, i+1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int k=0 ; k<course.size() ; k++) {
        int index = course[k];
        map<string, int> m;
        for(int i=0 ; i<orders.size() ; i++) { 
            // 미리 정렬해서 순서에 상관없게 만들기
            sort(orders[i].begin(), orders[i].end());
            check(orders[i], "", m, index, 0, 0);
        }
        vector<string> arr;
        int maxnum=0;
        for(map<string, int>::iterator it=m.begin() ; it!=m.end() ; it++) {
            if(it->second>=2) {
                if(maxnum<it->second) {
                    arr.clear();
                    arr.push_back(it->first);
                    maxnum = it->second;
                } else if(maxnum==it->second) {
                    arr.push_back(it->first);
                }
            }
        }
        for(int i=0 ; i<arr.size() ; i++) {
            answer.push_back(arr[i]);
        }
    }
    sort(answer.begin(), answer.end());
    
    return answer;
}