코딩테스트 : 메뉴 리뉴얼

이 문제는 손님들이 주문한 메뉴 조합을 분석하여, 가장 인기 있는 코스 메뉴 조합을 찾아내는 문제다.

orders의 각 주문에서 각 course 값에(메뉴 개수) 해당하는 메뉴 조합을 카운트한다.

이후 course 값에 대해 가장 많이 주문된 조합을 찾아서 2번 이상 주문되고 최대 주문 횟수를 가진 조합을 결과에 추가한다.

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

using namespace std;

// 재귀 함수: 조합 생성
void makeCourse(vector<char> v, string course, int target, vector<string>& result) {
		// 코스의 요리 갯수가 목표 갯수와 일치하면
    if (course.size() == target) 
    {
        //코스의 요리 갯수가 일치하면 result에 코스 저장
        result.push_back(course);
        return;
    }
    
    // v에서 각 요소를 선택하여 조합 생성
    for (size_t i = 0; i < v.size(); i++) 
    {
        //v를 필요한 범위만큼 잘라서 후속 문자만 선택
        makeCourse(vector<char>(v.begin() + i + 1, v.end()), course + v[i], target, result);  
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
		
		// course의 각 요소(코스에 포함될 요리 수)에 대해 반복
    for (int cnt : course) 
    {
        //코스가 가능한 항목 카운트
        map<string, int> orderCount;

        // 각 주문에서 해당 크기의 조합을 생성
        for (string order : orders) 
        {
            vector<char> orderChars(order.begin(), order.end());
            sort(orderChars.begin(), orderChars.end());  // 사전 순으로 정렬

            vector<string> combinations;  //코스가 가능한 항목을 담는 벡터
            makeCourse(orderChars, "", cnt, combinations);  // 해당 크기 조합 찾기

            // 생성된 각 코스의 주문 횟수 카운트
            for (string comb : combinations) 
            {
                orderCount[comb]++;
            }
        }

        // 가장 많이 나온 코스의 개수를 찾기
        int maxCount = 0;
        for (const auto& entry : orderCount) 
        {
            maxCount = max(maxCount, entry.second);
        }

        // maxCount와 일치하는 코스를 결과에 추가(가장 많이 주문된)
        for (const auto& entry : orderCount) 
        {
            if (entry.second == maxCount && maxCount >= 2) {  // 최소 2명이 주문한 경우만
                answer.push_back(entry.first);
            }
        }
    }

    sort(answer.begin(), answer.end());  // 사전 순으로 정렬
    return answer;
}

테스트 케이스

orders ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
course [2,3,4]
return ["AC", "ACDE", "BCFG", "CDE"]

orders ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]
course [2,3,5]
return ["ACD", "AD", "ADE", "CD", "XYZ"]

orders ["XYZ", "XWY", "WXA"]
course [2,3,4]
return ["WX", "XY"]


orders ["A", "B", "C", "D", "E"]
course [2]
return []