메뉴 리뉴얼

프로그래머스 - 메뉴 리뉴얼

문제 요약

---

• 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성
  → 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성
  → 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합을 후보에 포함
• 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return

제한사항

---

• 2 ≤ order 배열 크기 ≤ 20
• 2 ≤ order 원소 길이 ≤ 10
  - 각 문자열은 알파벳 대문자로 이루어져있음
  - 각 문자열에는 같은 알파벳 중복 X
• 1 ≤ course 배열 크기 ≤ 10
  - 2 ≤ course 원소 ≤ 10 인 자연수가 오름차순 정렬되어있음
  - course 배열 중복 X
• 정답은 문자열 형식으로 배열에 담아 사전순으로 오름차순 정렬 후 return
  - 배열 원소들도 알파벳 오름차순 정렬
  - 가장 많이 함께 주문된 메뉴 구성이 여러 개라면 모두 return
  - orders, course는 return 하는 배열의 크기가 1 이상이 되도록 주어짐
  

💡Idea

1. course 크기에 맞게 orders의 조합을 어떻게 구할까?
   → dfs를 통해 길이가 course가 되도록 하자
   → 길이를 만족한다면 map에 저장
2. map에 있는 것들 중 최댓값을 어떻게 구할까?
   → map을 vector로 옮긴 후 정렬

[ SourceCode ]

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

using namespace std;

map <string, int> kind;

void findAllCourse(string order, int len, string menus, int idx) {
    if(menus.length() == len) {
        kind[menus]++;
        return;
    }
   
    for(int i=idx; i<order.length(); i++) {
        findMenu(order, len, menus + order[i], i + 1);
    }
}

bool compare (pair<string, int> a, pair<string, int> b) {
    return a.second > b.second;
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
   
    for(int i=0; i<course.size(); i++) {
        kind.clear();
        for(int j=0; j<orders.size(); j++) {
            sort(orders[j].begin(), orders[j].end());
           
            if (course[i] <= orders[j].length()) {
                findMenu(orders[j], course[i], "", 0);
            }
        }
       
        vector <pair<string, int>> list(kind.begin(), kind.end());
        sort(list.begin(), list.end(), compare);
       
        if (!list.empty()) {
            int cnt = list[0].second;

            if (cnt > 1) {
                for (int j = 0; j < list.size(); j++) {
                    if (list[j].second == cnt) {
                        answer.push_back(list[j].first);
                    }
                    else {
                        break;
                    }
                }
            }
        }
    }

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

    return answer;
}

Feedback

---

1. 처음에 조합을 구하는 방법이 떠오르지 않아 단순 반복을 생각했다.
   → dfs로 쉽게 구할 수 있다는 것을 알게 됨,,
   → 이때 map을 사용하면 정말 편하다 !!!