KAKAO기출 [메뉴 리뉴얼]

문제 설명

식당에서 손님이 시켰던 단품 요리를 기준으로 코스요리를 구성하려 한다.

조건

• 최소한 2명 이상의 손님으로부터 주문되어야 한다.
• 메뉴 구성은 문자열 오름차순으로 한다.
• 가장 많이 주문된 메뉴를 추가함(여러개일 경우 다 추가한다.)

해결 방법

1. 각 손님별로 받은 주문내역을 문자열 순으로 정렬한다.

 for(int i=0;i<orders.size();i++){
        sort(orders[i].begin(),orders[i].end());
        tmp=orders[i];
        back("",0);
    }

2. 백트래킹을 이용하여 랜덤선택한 문자열을 고른 후 각 크기별 map에 존재한다면 value++해주고, 존재하지 않는다면 value를 1로 하여 map에 새롭게 추가해준다.

void back(string s,int x){
    
    if(x!=tmp.length()){
        back(s,x+1);
        s+=tmp[x];
        int len=s.length();
    if(len>=2){
        if(m[len].find(s)==m[len].end()){
            m[len].insert(make_pair(s,1));
        }else{
            m[len][s]++;
        }
    }
        back(s,x+1);
    }
}

3. 주어진 코스 크기별 map을 조사하여 vector화 해준 후, value 값을 기준으로 내림차 정렬을 해준다. 이후에 맨 앞쪽의 메뉴를 answer에 추가해준다.

for(int i=0;i<course.size();i++){
        int k = course[i];
        vector<pair<string,int>> v(m[k].begin(),m[k].end());
        sort(v.begin(),v.end(),cmp);
        if(v.size()!=0&&v[0].second>=2){
            int com=v[0].second;
            for(int j=0;j<v.size();j++){
                if(v[j].second==com){
                    answer.push_back(v[j].first);
                    
                }else{
                    break;
                }
            }
        }
        
        
    }

4. answer을 sorting하고 마무리

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

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;
string tmp;
set<string> ss;
map<string,int> m[11];
bool cmp(const pair<string,int>& a, const pair<string,int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

void back(string s,int x){
    
    if(x!=tmp.length()){
        back(s,x+1);
        s+=tmp[x];
        int len=s.length();
    if(len>=2){
        if(m[len].find(s)==m[len].end()){
            m[len].insert(make_pair(s,1));
        }else{
            m[len][s]++;
        }
    }
        back(s,x+1);
    }
}

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());
        tmp=orders[i];
        back("",0);
    }
   
    map<string,int>::iterator iter;
    for(int i=0;i<course.size();i++){
        int k = course[i];
        vector<pair<string,int>> v(m[k].begin(),m[k].end());
        sort(v.begin(),v.end(),cmp);
        if(v.size()!=0&&v[0].second>=2){
            int com=v[0].second;
            for(int j=0;j<v.size();j++){
                if(v[j].second==com){
                    answer.push_back(v[j].first);
                    
                }else{
                    break;
                }
            }
        }
//         for(int j=0;j<v.size();j++){
//             cout<<v[j].first<<" "<<v[j].second<<endl;
             
//         }
        
        
    }
    // for(iter=m[2].begin();iter!=m[2].end();iter++){
    //     cout<<iter->first<<endl;
    // }
    sort(answer.begin(),answer.end());
    return answer;
}