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

프로그래머스

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders,

추가하고 싶은 코스 요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매게변수로 주어질 때,

새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 담아 반환해주세요.

 

(단품메뉴 2개인 코스요리를 만들고 싶을 때,

만들 수 있는 세트중 가장 많이 판매된 세트를 추가하여 반환합니다.)

 

 

풀이 방법

아래 3단계를 통해 풀이합니다.

1. 조합 만들기 (ABCD -> 갯수가 2인 세트 = [A,B], [A,C], [A,D], [B,C], [B,D], [C,D])

2. 개수별 가장 많이 팔린 세트 찾기

3. 해당 세트를 배열에 집어넣기

 

1. 조합 만들기

void GetMenuCombi(vector<string>& result, string& order, int num, string str = "", int idx = 0)
{
    if (str.size() == num)
    {
        result.push_back(str);
        return;
    }
    
    for (int i = idx; i < order.size(); i++)
        GetMenuCombi(result, order, num, str + order[i], i + 1);
}

 

주문 목록 order과 만드려는 세트메뉴의 단품메뉴 수를 넣으면 조합이 반환되는 함수입니다.

재귀 되어 result에 채워지도록 하였으며

해당 함수를 호출하기 전에 order를 정렬 후에 보내줘야합니다. ( 정렬하지 않으면 AB, BA 둘 다 생성됨 )

 

map<string, int> combiCnt;
    
for (string order : orders)
{
    sort(order.begin(), order.end());
    for (int n : course)
    {
        vector<string> combis;
        GetMenuCombi(combis, order, n);

        for (string combi : combis)
            combiCnt[combi]++;
    }
}

map을 이용하여 만들 수 있는 모든 조합을 찾아주었고 map의 value에는 중복된 횟수를 넣어주었습니다.

 

 

2. 개수 별 가장 많이 팔린 세트 찾기

map<int, pair<int, vector<string>>> ans;
for (auto c : combiCnt)
{
    string str = c.first;
    int len = c.first.size();
    int cnt = c.second;

    if (cnt == 1)
        continue;

	// 현재 세트 메뉴가 더 많이 팔렸다면 배열 초기화
    if (ans[len].first < cnt)
    {
        ans[len].first = cnt;
        ans[len].second.clear();        
    }

    if (ans[len].first == cnt)
        ans[len].second.push_back(str);
}

map을 이용하여 해결하였습니다.

map<세트 메뉴의 단품 수, pair<팔린 횟수, 세트 메뉴들>>

중복된 횟수가 같은 세트 메뉴의 경우는 모두 출력해줘야 하기 때문에 배열로 만들었습니다.

 

하나의 반복문으로 해결하려 했기에 이런 복잡한 map이 나오게 되었는데

2중 for문을 사용한다면 아래처럼 더욱 깔끔하게 해결할 수 있을 것 같습니다.

vector<string> answer;
for (auto len : course)
{
    int sellCnt = 0;
    vector<string> combis;
    for (auto [str, cnt] : combiCnt)
    {
        if (str.size() != len || cnt == 1)
            continue;

        if (sellCnt < cnt)
        {
            sellCnt = cnt;
            combis.clear();
        }

        if (sellCnt == cnt)
            combis.push_back(str);
    }
    answer.insert(answer.end(), combis.begin(), combis.end());
}

 

3. 해당되는 세트를 집어넣기

vector<string> answer;

for (auto [len, p] : ans)
{
    for (string str : p.second)
        answer.push_back(str); 
}

2번에서 map을 사용한 경우에 해당합니다.

저장된 배열을 하나의 배열에 옮겨담아줍니다.

 

 

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

마지막으로 정렬 후, 반환해주면 됩니다.

 

 

정답 코드

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

using namespace std;

void GetMenuCombi(vector<string>& result, string& order, int num, string str = "", int idx = 0)
{
    if (str.size() == num)
    {
        result.push_back(str);
        return;
    }
    
    for (int i = idx; i < order.size(); i++)
    {
        GetMenuCombi(result, order, num, str + order[i], i + 1);
    }
    
}

vector<string> solution(vector<string> orders, vector<int> course) {
    
    map<string, int> combiCnt;
    
    for (string order : orders)
    {
        sort(order.begin(), order.end());
        for (int n : course)
        {
            vector<string> combis;
            GetMenuCombi(combis, order, n);
            
            for (string combi : combis)
                combiCnt[combi]++;
        }
    }
    
    map<int, pair<int, vector<string>>> ans;
    for (auto c : combiCnt)
    {
        string str = c.first;
        int len = c.first.size();
        int cnt = c.second;
        
        if (cnt == 1)
            continue;
        
        if (ans[len].first < cnt)
        {
            ans[len].first = cnt;
            ans[len].second.clear();        
        }
        
        if (ans[len].first == cnt)
            ans[len].second.push_back(str);
    }
    
    vector<string> answer2;
    for (auto len : course)
    {
        int sellCnt = 0;
        vector<string> combis;
        for (auto [str, cnt] : combiCnt)
        {
            if (str.size() != len || cnt == 1)
                continue;
            
            if (sellCnt < cnt)
            {
                sellCnt = cnt;
                combis.clear();
            }
            
            if (sellCnt == cnt)
                combis.push_back(str);
        }
        answer2.insert(answer2.end(), combis.begin(), combis.end());
    }
    
    
    vector<string> answer;
    
    for (auto [len, p] : ans)
    {
        for (string str : p.second)
            answer.push_back(str); 
    }
    
    sort(answer.begin(), answer.end());
    sort(answer2.begin(), answer2.end());
    return answer2;
}