[c++] 프로그래머스 - 메뉴 리뉴얼(Level 2)

문제

코딩테스트 연습 - 메뉴 리뉴얼

 

코드

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


using namespace std;

map<string,int>cnt;
map<int,int>len_max;

vector<string>combi_arr;

void combination(int index, string combi, string origin, int max_len){
    for(int i=index; i<max_len; i++){
        string inp = combi+origin[i];
        combi_arr.push_back(inp);
        combination(i+1, inp, origin, max_len);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(string order:orders){
        set<string>ncr;
        
        for(int i=0; i<order.length(); i++) combination(i,  "", order, order.length());
        for(string &combi:combi_arr) sort(combi.begin(),combi.end());
        for(string combi:combi_arr) ncr.insert(combi);     
        for(auto it=ncr.begin(); it!=ncr.end(); it++) cnt[*it]++;
        
        combi_arr.clear();
    }
    
    for(auto it = cnt.begin(); it!=cnt.end(); it++){
        int len = (it->first).length();
        if(len_max[len]<it->second) len_max[len] = it->second;
    }
    for(auto it = cnt.begin(); it!=cnt.end(); it++){
        for(int cos:course){
            if(it->second>=2&&(it->first).length()==cos&&it->second==len_max[(it->first).length()]){
                answer.push_back(it->first);
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}

 

풀이(45분 이상)

처음에 아래와 같이 코드를 작성했었는데 시간 초과 때문에 50점이 떠서 굉장히 고민을 많이 한 문제입니다.

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


using namespace std;

map<string,int>cnt;
map<int,int>len_max;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(string &order:orders) sort(order.begin(),order.end());  //미리 정렬
    
    for(string order:orders){
        map<string,int>visited;
        set<string>ncr;
        do{
            string ord = order;
            while(!ord.empty()){
                ncr.insert(ord);
                ord.pop_back();
            }
        }while(next_permutation(order.begin(),order.end()));
        
        for(auto it=ncr.begin(); it!=ncr.end(); it++){
             string inp = *it;
             sort(inp.begin(),inp.end());
            if(!visited[inp]){
                cnt[inp]++;
                visited[inp]=1;
            }
        }
    }
    
    for(auto it = cnt.begin(); it!=cnt.end(); it++){
        int len = (it->first).length();
        if(len_max[len]<it->second) len_max[len] = it->second;
    }
    for(auto it = cnt.begin(); it!=cnt.end(); it++){
        for(int cos:course){
            if(it->second>=2&&(it->first).length()==cos&&it->second==len_max[(it->first).length()]){
                answer.push_back(it->first);
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}

손님마다 주문할 수 있는 모든 경우의 수를 구해야 하는데 좀 편하게 해 보자고 next_permutation을 사용한 것이 시간 초과의 원인이었습니다. 시간 초과 뜨자마자 바로 백트랙킹으로 구현을 하면 좋았을 텐데 또 쓸데없는 고집 때문에 next_permutation을 사용해서 억지로 어떻게든 해보려고 이것저것 건드린 게 시간낭비가 매우 컸습니다..에휴,.. 고집을 좀 줄여야겠습니다.