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

https://programmers.co.kr/learn/courses/30/lessons/72411

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

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

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    map<string, int> m;
    vector<int> maxes(11,1);
    for (int i=0; i<orders.size(); i++){
        sort(orders[i].begin(), orders[i].end());
        //분해하고 map에 넣기
        for (int j=0; j<course.size(); j++){
            int n=course[j];
            if (orders[i].size()<n){
                continue;
            }
            vector<bool> temp(n,true);
            temp.insert(temp.end(), orders[i].size()-n,false);
            do{
                string s="";
                for (int k=0; k<orders[i].size(); k++){
                    if (temp[k]){
                        s+=orders[i][k];
                    }
                }
                m[s]++;
            } while (prev_permutation(temp.begin(), temp.end()));
        }
    }
    map<string,int>::iterator it;
    for (it=m.begin(); it!=m.end(); it++){
        int len=(it->first).size();
        if (maxes[len]<(it->second)){           //각 course 당 최대 주문 횟수 뽑아오기
            maxes[len]=it->second;
        }
    }
    for (it=m.begin(); it!=m.end(); it++){
        int len=(it->first).size();
        if (maxes[len]>1 && maxes[len]==it->second){    //최대 주문횟수 가지는 조합 가져오기
            answer.push_back(it->first);
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

순열조합만 나오면.. 벌벌 떠는 사람.. 저에요...✋

 

이 문제의 포인트는 

orders에서 course 수대로 뽑아 조합을 구해 특정 조합이 몇 개 주문되었는지 체크하는 것이다.

 

각 order 마다, 정해진 course 가지를 뽑는 조합들을 구한다.

그리고 map 에 이 조합(문자열 형태)을 넣어주고, increment 해주어서 횟수를 알 수 있도록 한다.

반복문을 돌 때, order -> course 이렇게 했는데 이렇게 하면, 나중에 따로 course 별로 최대 주문 횟수를 구해줘야 되고, 최대 주문 횟수를 가지는 조합이 무엇인지 또 찾아야 한다. 비효율적이다.

 

course->order 로 반복문을 돌아주면, course 별로 자동으로 최대 주문 횟수를 구할 수 있고, course 별로 다 끝마치면 map을 clear 해주면 된다.

 

또한 조합을 구할 때 prev_permutation 을 사용했다. course 개만큼 vector에 true 넣어주고 +남은 건(orders[i].size()-course[j]) false 넣어준다. 이 vector가 돌아가면서 전체 course 개를 뽑는 조합을 저장하고, 이를 맵에 넣는다. 

 

그런데 조합을 재귀적으로 구해줘도 된다.

 

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

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

void combination(string src, string crs, int depth) {
    if (crs.size() == depth) combi[crs]++;

    else for (int i = 0; i < src.size(); i++)
        combination(src.substr(i+1), crs+src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    for (string &order : orders)
        sort(order.begin(), order.end());

    for (int crs : course) {
        for (string order : orders)
            combination(order, "", crs);

        int sup = 0;
        for (auto it : combi)
            sup = max(sup, it.second);
        for (auto it : combi)
            if (sup >= 2 && it.second == sup)
                answer.push_back(it.first);
        combi.clear();
    }

    sort(answer.begin(), answer.end());
    return answer;
}

출처: 프로그래머스 최승욱 , 김수진 , 정순영 님

 

여기서는 course 반복문을 먼저 돌고, 전체 orders 에서 k개를 뽑는 조합을 구해주고, 그 조합에서 최대 빈도로 나온 애들을 answers 에 넣어주는 식이다.

 

조합을 구하는 위 재귀 형태를 잘 기억할것