프로그래머스 - 메뉴 리뉴얼 (Cpp)

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

문제 풀이

처음에 문자열 비교로 접근해 엄청 해멨다. 이 문제는 문자열 비교로 접근을 하는게 아니라 한 사람이 시킨 메뉴 코스를 이용해 만들 수 있는 경우의 수를 만들어 비교하는 문제다.

1. 코스를 사전 순서로 저장할 수 있도록 주문을 정렬해준다.
2. 한 손님이 주문한 단품 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다.
3. 코스내 메뉴 개수에 따라 가장 많이 선택된 횟수를 저장해 놓는다.
4. 코스를 선택할때 코스내 메뉴가 메뉴 개수에서 가장 많이 선택된 횟수와 같다면 넣어준다.

모든 코스 조합을 만들어주는 함수

void makeAllCourse(string subOrder, string order, int depth) {
    if (depth > order.size()) {
        return;
    }

    if (depth == order.size() && subOrder.size() > 1) {
        if (m.find(subOrder) == m.end()) {
            m[subOrder] = 1;
        } else {
            m[subOrder] += 1;
        }
    }
    // 현재 메뉴를 선택하고 다음 메뉴로 넘어간다.
    makeAllCourse(subOrder + order[depth], order, depth + 1);
    // 현재 메뉴를 선택하지 않고 다음 메뉴로 넘어간다.
    makeAllCourse(subOrder, order, depth + 1);
}

전체 소스

#include <bits/stdc++.h>
using namespace std;

map<string, int> m;
int maxValues[100];

void makeAllCourse(string subOrder, string order, int depth) {
    if (depth > order.size()) {
        return;
    }

    if (depth == order.size() && subOrder.size() > 1) {
        if (m.find(subOrder) == m.end()) {
            m[subOrder] = 1;
        } else {
            m[subOrder] += 1;
        }
    }

    makeAllCourse(subOrder + order[depth], order, depth + 1);
    makeAllCourse(subOrder, order, depth + 1);
}

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

    for (int i = 0; i < orders.size(); i++) {
        sort(orders[i].begin(), orders[i].end());
        makeAllCourse("", orders[i], 0);
    }
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        int courseCount = iter->first.length();
        maxValues[courseCount] = max(maxValues[courseCount], iter->second);
    }
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        int courseCount = iter->first.length();

        if (iter->second == maxValues[courseCount] && iter->second >= 2) {
            for (int i = 0; i < course.size(); i++) {
                if (courseCount == course[i]) {
                    answer.push_back(iter->first);
                }
            }
        }
    }
    return answer;
}