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

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

프로그래머스

 

풀이

손님이 시킨 단일메뉴 조합 orders 와 "스카피"가 만들고자 하는 세트 메뉴의 단일 메뉴 개수 course 가 주어질 때, course 개수에 맞는 세트 메뉴 구성을 반환해야 하는 문제입니다.

 

깊이 우선 탐색을 활용해 문제를 해결할 수 있으며, 정렬을 잘 활용해야 하는 문제입니다.

알고리즘은 다음과 같습니다.

course를 순회하며 orders중 하나가 주어졌을 때 course의 크기 i 보다 크기가 같거나 크다면 메뉴 조합(dfs함수)를 수행합니다. dfs 종료 조건은 course의 크기 i와 만들어진 임의의 세트 구성의 크기 res.size() 가 같을 경우 res를 정렬 후 map에 추가해줍니다. 이 때, 2번 이상 주문된 조합인지 판별해야 하므로 map의 value는 int 형입니다.

 

dfs가 끝나면 vector 자료형에 map을 넣고 value에 대해 내림차순으로 정렬해줍니다(가장 많이 나온 조합). 그 후, v를 순회하며 많이 나온 메뉴만 (중복 포함이므로 >= max) answer에 push_back 해줍니다. 

이후, answer를 다시 오름차순 정렬해서 return 하면 정답이 완성됩니다.

 

리뷰

map  자료구조를 애초에 value에 대해 내림차순 정렬하는 방식으로 선언하고 싶었지만 방법이 없는 것 같습니다. 따라서 v에 copy 한 후 정렬하거나, 우선순위 큐 자료구조를 선언하여 풀이할 수도 있을 것 같습니다.  

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

using namespace std;

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

void dfs(map<string, int>& map, int size, int idx, string s, string res)
{
    if (res.size() == size) {
        sort(res.begin(), res.end());
        map[res]++;
        return;
    }
    
    for (int i = idx; i < s.size(); i++) {
        res += s[i];
        dfs(map, size, i+1, s, res);
        res.pop_back();
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // 모든 조합 탐색
    for (auto i : course) {
        map<string, int> m;
        for (int j = 0; j < orders.size(); j++) {
            if (orders[j].size() >= i) {
                // 조합
                string res;
                dfs(m, i, 0, orders[j], res);
            }
        }
        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), cmp);
        int max = 0;
        for (auto cs : v) {
            if (cs.second >= 2 && cs.second >= max) {
                answer.push_back(cs.first);
                max = cs.second;
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}