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

 이 문제는 맵, 백트래킹, 정렬을 이용해서 풀었다. 일단 입력으로 주어지는 배열들이 매우 작으므로, 백트래킹을 사용해도 시간 초과가 나지 않는다. 이 문제는 단순히 문제에서 주어진 대로 구현하면 되지만, 몇 가지 주의할 사항이 있다. 첫번째로 백트래킹을 할 때, temp와 limit가 같아질 때 cnt 맵에 +1을 하게 되는데, 이 때 temp는 정렬되어 있어야 한다. 만약 temp가 XW인 경우에, WX가 카운트되어야 하는 것이다. 두번째로, 모든 연산이 끝난 후에도 answer 배열이 한번 더 정렬되어야 한다. 이 두개만 주의한다면 구현은 어렵지 않게 할 수 있다.

 

 

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

using namespace std;

map<string, int> cnt;

void solve(string& order, int limit, int prev, string temp) {
    int size = order.size();
    
    if (temp.size() == limit) {
        sort(temp.begin(), temp.end());
        cnt[temp]++;
        return;
    }
    
    if (prev == -1) {
        for (int i = 0; i < size; i++) {
            solve(order, limit, i, temp + order[i]);
        }
        
        return;
    }
    
    for (int i = prev + 1; i < size; i++) {
        solve(order, limit, i, temp + order[i]);
    }
}

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

vector<pair<string, int>> result[11];
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    for (string& order : orders) {
        for (int c : course) {
            solve(order, c, -1, "");
        }
    }
    
    map<string, int>::iterator iter;
    for (iter = cnt.begin(); iter != cnt.end(); iter++) {
        if ((iter->second) >= 2) {
            result[(iter->first).size()].push_back({(iter->first), (iter->second)});
        }
    }
    
    for (int c : course) {
        sort(result[c].begin(), result[c].end(), compare);
        
        if (result[c].empty()) {
            continue;
        }
        
        int tempCnt = result[c].front().second;
        
        for (int i = 0; i < result[c].size(); i++) {
            if (tempCnt == result[c][i].second) {
                answer.push_back(result[c][i].first);
                continue;
            }
            
            if (tempCnt > result[c][i].second) {
                break;
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}