메뉴리뉴얼

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

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

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

map<string,int>m; // 조합을 통해 구한 것을 +1 해주는 map
map<int,int>maxNum; // 각 자리수의 최대값을 저장
vector<vector<string>>maxList(11); // 자리수 별로 최대값을 만족하는 string 저장

void dfs(string order, int course, int idx, string str){
    int sz = str.size();
    if(sz==course){
        m[str]++;
        if(m[str]>=2 && maxNum[sz]<m[str]){
            maxNum[sz] = m[str]; // 최대값 갱신
            maxList[sz].clear();
            maxList[sz].push_back(str);
        }
        else if(m[str]>=2 && maxNum[sz]==m[str]){
            maxList[sz].push_back(str);
        }
        return;
    }
    
    for(int i=idx; i<order.size(); i++){
        dfs(order,course,i+1,str+order[i]);
    }
    
    
}



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());
        
        for(int j=0; j<course.size(); j++){
        
            dfs(orders[i],course[j],0,"");
            
        }
    }
    
    for(int i=0; i<course.size(); i++){
        int sz = course[i];
        for(int j=0; j<maxList[sz].size(); j++){
            answer.push_back(maxList[sz][j]);
        }
        
    }
    
    sort(answer.begin(),answer.end());
    
    return answer;
}

참고: yjyoon-dev.github.io/kakao/2021/01/30/kakao-menurenewal/

[프로그래머스] 메뉴 리뉴얼 문제 풀이 (2021 카카오 코딩테스트)

 

 

<처음 코드> - 틀린 코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
vector<string>answer;
map<int,int>m;
map<int,vector<string>>list;
void ordersSearch(vector<string> orders, string coarse){
    
    int cnt=0;
    int sz = coarse.size();
    
    for(int i=0; i<orders.size(); i++){
        for(int j=0; j<coarse.size(); j++){
            char ch[2];
            ch[0]=coarse[j];
            string str(ch);
            if(orders[i].find(str)!=string::npos){
                if(j==coarse.size()-1){cnt++;}
            }
            else{break;}
        }
    }
    
    if(cnt>=2 && cnt>m[sz]){ m[sz]=cnt; list[sz].clear(); list[sz].push_back(coarse);}
    else if(cnt>=2 && cnt==m[sz]){
 
        list[sz].push_back(coarse);
    }
    

}


void dfs(vector<string> orders,vector<char>v, string coarse , int count, int limit, int idx){
    
    if(count == limit){
        ordersSearch(orders, coarse);
        return;
    }
    
    for(int i=idx; i<v.size();i++ ){
        
        char ch[2];
        ch[0]=v[i];
        string str(ch);
        dfs(orders,v,coarse+str,count+1,limit,i+1);
        
    }
    
}




vector<string> solution(vector<string> orders, vector<int> course) {
//    vector<string> answer;
    
   set<char>s;
    
    for(int i=0; i<orders.size(); i++){
        
        string order = orders[i];
        
        for(int j=0; j<order.size(); j++){
            
            s.insert(order[j]);
            
        }
    }
    
    vector<char>v;
    
    set<char>::iterator it;
    
    for(it=s.begin(); it!=s.end(); it++){
        v.push_back(*it);
    }
    
  //  sort(v.begin(),v.end());
    
    for(int i=0; i<course.size(); i++){
             dfs(orders,v,"",0,course[i],0);
    }
    
    
    map<int,vector<string>>::iterator mit;
    
    for(mit=list.begin();mit!=list.end(); mit++){
        vector<string>vs = mit->second;
        for(int i=0; i<vs.size(); i++){
            answer.push_back(vs[i]);
        }
    }
    sort(answer.begin(),answer.end());
    
    return answer;
}