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

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

using namespace std;

map<string, int> m;

void cal(string order, string tmp, int idx, int target) {
    if (tmp.size() == target) {
        m[tmp]++;  
        return;
    }
    
    for (int i = idx; i < order.size(); i++) {
        cal(order, tmp + order[i], i + 1, target);
    }
}

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

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

    for (auto i : course) {  
        m.clear();  
        for (auto order : orders) 
        {
            if (order.size() >= i) cal(order, "", 0, i);
        }

        int maxCount = 0;
        for (auto i : m) {
            maxCount = max(maxCount, i.second);
        }

        for (auto i : m) {
            if (i.second == maxCount && maxCount >= 2) {
                answer.push_back(i.first);
            }
        }
    }

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

 

orders 목록에서 course 길이에 맞는 조합을 찾아서 카운팅을 하게 된다.

이를 위해서 orders 목록을 우선 정렬 하여 일관된 결과를 갖도록 해줄 필요가 있다.

에시
["XYZ", "XWY", "WXA"]

XWY에서 -> XW
WXA에서 -> WX

조합을 찾는 것이기에 같은 케이스 이나, 정렬되지 않아 추후 Map에서 같은 값으로 카운팅 불가

 

정렬 할때는 &를 붙여 복사본이 아닌 원본이 정렬되도록 해준다.

이는 다른 함수에서 정렬된 내용을 사용하기 때문에 필요하다.

 

이제 course의 각 값(i)만큼 체크해줄 차례이다.

order 사이즈가 course의 i 값보다 크거나 같다면 해당 order를 기준으로 i 값 만큼의 길이를 가진 경우를 계산해야 한다.

이를 재귀 형태로 구현하게 된다.

기본 문자열, 더해진 문자열, 인덱스 값, i 값을 인자로 갖게 되며 기본 문자열에서 하나씩 더해가며 만든 문자열이 i 값과 같아지는 순간의 문자열을 카운팅 해주면 된다.

가능한 모든 조합을 찾기 위해 재귀 함수에서도 반복문을 통해 시작 인덱스를 구별하여, 모든 인덱스부터 시작해 재귀를 돌리도록 해준다.

 

이제 가장 많이 주문된 순서로 메뉴 구성을 해야하기 때문에 map에서 카운팅 값 중 가장 큰 값을 찾아준다.

이를 토대로 코스에 해당하는 문자열을 넣어주면 되는데, 이때 주의할 점은 최소 2명 이상의 손님으로부터 주문되어야 하므로 maxCount가 2 이상이어야만 한다.

 

마지막으로 문제에 주어진 조건에 따라 정답이 담긴 벡터를 최종 정렬해준다.