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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    map<string, int> dishes;
    
    for(int i=0; i<orders.size(); i++){
        sort(orders[i].begin(), orders[i].end());
        for(int j=0; j<course.size(); j++){
            int n = course[j];
            
            if(orders[i].size() < n){
                continue;
            }
            
            string bitmask(n, 1);
            bitmask.resize(orders[i].size(), 0);
            
            do{
                string dish = "";
                for (int k = 0; k < bitmask.size(); k++) {
                    if (bitmask[k]) {
                        dish += orders[i][k];
                    }
                }
                dishes[dish]++;
            }while(prev_permutation(bitmask.begin(), bitmask.end()));
        }
    }
    
    for(int i=0; i<course.size(); i++){
        int n = course[i];
        int maxCount = 0;
        vector<string> maxDishes;
        
        for(auto dish : dishes){
            if (dish.first.size() == n && dish.second >= 2){
                if (dish.second > maxCount) {
                    maxCount = dish.second;
                    maxDishes = {dish.first};
                } else if (dish.second == maxCount) {
                    maxDishes.push_back(dish.first);
                }
            }
        }
        
        for(auto maxDish : maxDishes){
            answer.push_back(maxDish);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

---

📝 풀이

각 주문에 대하여 prev_permutation 함수와 비트마스크를 이용하여 가능한 단품 메뉴 조합을 구합니다.

순열을 구하기 전에 주문을 오름차순으로 정렬하고 비트마스크를 코스의 수만큼 지정합니다.

만약 주문의 길이가 구하고자하는 코스의 수보다 적다면 구하지 않고 다음 과정으로 넘어갑니다.

구한 조합들은 dishes map에 카운팅하며 저장합니다.

 

이 과정까지 진행된 예제 3번의 dishes map을 출력하면 다음과 같습니다.

AX	1
AWX	1
AX	1
WX	2
WXY	1
WY	1
XY	2
XYZ	1
XZ	1
YZ	1

 

가장 많이 주문된 단품 메뉴로 코스를 구성하기 위하여 dishes map을 확인합니다.

메뉴의 개수가 코스 요리의 개수와 같고 2번 이상 주문된 dish들만 최댓값을 비교합니다.

최댓값을 비교할 때 주의할 점은 클 경우는 이전 메뉴들을 없애야 하지만 최댓값과 동일하면 추가해야 하는 점입니다.

가장 많이 주문된 단품 메뉴들을 answer에 추가합니다.

 

최종적으로 오름차순으로 answer을 정렬한 후 return 합니다.