C++ (코딩테스트) - 메뉴 리뉴얼(프로그래머스)

문제

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

프로그래머스

 

 

나의 풀이

 

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

using namespace std;

void Combination(string arr, vector<char> comb, int r, int index, int depth, vector<string>* con)
{
    if (r == 0)
    {
        string temp;
        for (int i = 0; i < comb.size(); i++)
            temp.push_back(comb[i]);
        con->push_back(temp);
    }
    else if (depth == arr.size())
    {
        return;
    }
    else
    {
        comb[index] = arr[depth];
        Combination(arr, comb, r - 1, index + 1, depth + 1, con);
        Combination(arr, comb, r, index, depth + 1, con);
    }
}

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

    //오름차순으로 만들기
    for (int i = 0; i < orders.size(); i++) 
        sort(orders[i].begin(), orders[i].end());

    for (int j = 0; j < course.size(); j++)
    {
        //course 갯수만큼 메뉴 담기
        vector<vector<string>> con;
        for (int k = 0; k < orders.size(); k++)
        {
            vector<string> m_con;
            vector<char> comb(course[j]);
            Combination(orders[k], comb, course[j], 0, 0, &m_con);
            con.push_back(m_con);
        }

        //곂치는 코스 체크
        vector<string> vec_temp;
            int max_cnt = 0;
        for (int a = 0; a< con.size() - 1; a++)
        {
            for (int b = 0; b < con[a].size(); b++)
            {
                bool chk = false;
                string temp = con[a][b];
                int cnt = 1;
                if (temp == "") continue;
                con[a][b].clear();
                for (int c = a + 1; c < con.size(); c++)
                {
                    for (int d = 0; d < con[c].size(); d++)
                    {
                        if (temp == con[c][d])
                        {
                            cnt++;
                            chk = true;
                            con[c][d].clear();
                        }
                    }
                }
                if(!chk) continue;
                if (cnt < max_cnt)continue;

                if (cnt > max_cnt)
                {
                    vec_temp.clear();
                    max_cnt = cnt;
                }
                vec_temp.push_back(temp);
            }
        }
        vector<string>::iterator it = answer.insert(answer.end(), vec_temp.begin(), vec_temp.end());
    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

다른사람 풀이(추천수 높음)

 

#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;
}