[프로그래머스 Lv.2] 메뉴 리뉴얼

[문제]

 

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

프로그래머스

 

[풀이]

 

가끔 보면 문제를 보자마자 힌트가 보이는 것들이 있습니다. 해당 문제가 그런데, orders의 크기(갯수)와 각 요소마다의 문자열 길이를 보면 이런 문제는 그냥 완전 탐색을 진행해도 됩니다.

 

근데 문제가 course를 선택해서 가장 많은 조합을 도출하라고 했으니, 아예 다 돌 필요는 없습니다. 일단 모든 orders를 취합해서 문자열들(메뉴들)이 뭐가 있는지를 파악합니다. 이후 이 문자열들에서 course 갯수만큼 추출해서 모든 요소들을 검사하고, 이 조합을 선택하는 orders가 몇개인지 파악합니다. 예를 들어 AB를 탐색하기로 했으면 ABCFG에서 AB가 있는지 없는지, AC에서 AB가 있는지 없는지를 파악하는 것입니다.

 

이렇게 2개 조합일 때, 3개 조합일 때, 4개 조합일 때 모두 파악한 뒤 가장 많은 선택을 받았던 조합을 answer에 담고 오름차순 정렬해준 뒤 return 해줍니다.

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

using namespace std;

// 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성
// 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함
// orders.size() : 2 이상 20 이하
// orders[i] : 2 이상 10 이하인 문자열, 대문자로만, 같은 알파벳이 중복해서 들어있지 않습니다
// course.size() : 1 이상 10 이하
// course[i] : 2 이상 10 이하인 자연수가 오름차순으로 정렬
// 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return
// 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return
vector<string> solution(vector<string> orders, vector<int> course) 
{
    vector<string> answer;
    map<char, int> Map;
    vector<char> Menus;

    for (size_t i = 0; i < orders.size(); i++)
    {
        for (size_t j = 0; j < orders[i].size(); j++)
        {
            char CurMenu = orders[i][j];
           
            if (Map.find(CurMenu) == Map.end())
            {
                Map.insert(make_pair(CurMenu, 1));
                Menus.push_back(CurMenu);
            }
        }
    }

    sort(Menus.begin(), Menus.end());

    // 원하는 조합 개수에 대해 순회
    for (int c : course)
    {
        unordered_map<string, int> CombCount;
        int MaxCount = 0;

        for (const string& order : orders)
        {
            if (order.size() < c) continue;

            string SortedOrder = order;
            sort(SortedOrder.begin(), SortedOrder.end());

            vector<bool> Select(SortedOrder.size(), false);
            fill(Select.end() - c, Select.end(), true);

            do
            {
                string Comb;
                for (int i = 0; i < SortedOrder.size(); ++i)
                {
                    if (Select[i])
                        Comb += SortedOrder[i];
                }

                CombCount[Comb]++;
                MaxCount = max(MaxCount, CombCount[Comb]);

            } while (next_permutation(Select.begin(), Select.end()));
        }

        // 가장 많이 등장한 조합만 answer에 추가
        for (const auto& it : CombCount)
        {
            const string& comb = it.first;
            int count = it.second;

            if (count >= 2 && count == MaxCount)
            {
                answer.push_back(comb);
            }
        }
    }

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

    return answer;
}