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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72411

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

1. 주의할 점

- Set을 적절히 사용하며 정렬을 잘 활용해야 한다

 

2. 구현

- 만들 메뉴의 수를 Len set에 저장한다

- Orders 벡터에 있는 원소를 정렬하며, 원소 자체(문자열)도 정렬한다

- Orders 벡터에 있는 원소로 만들 수 있는 메뉴 구성을 DFS() 함수를 통해 생성하며, 만약 able의 길이가 Len에 포함된 숫자와 같다면 S set에 포함시킨다

- S set에 있는 원소(메뉴조합)를 Orders 원소 모두와 비교하며 Ordres에 해당 원소가 속해 있으면서 그런 수가 2개 이상이면 V[] 벡터에 비교를한다

- V[idx] 벡터를 통해 idx개의 조합을 가진 메뉴가 몇 번 호출되었으며, 어떤 조합의 메뉴인지 저장한다

- V[] 벡터에 있는 원소를 모두 Answer 벡터에 넣고 정렬한다  

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
struct info{
    string str;
    int cnt;
};

set<int> len;
set<string> s;
vector<info> v[11];

void dfs(string able, string str, int idx){
    int cnt = able.size();
    if(len.find(cnt)!=len.end())    s.insert(able);
    if(cnt==str.size()) return;
    for(int i=idx+1;i<str.size();i++)
        dfs(able+str[i],str,i);
}

bool comp(string a, string b){
    int aidx = 0;
    int bidx = 0;
    while(aidx<a.size() && bidx<b.size()){
        if(a[aidx]==b[bidx]){
            aidx++;
            bidx++;
        }
        else bidx++;
    }
    return aidx == a.size() ? true : false;
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0;i<course.size();i++)
        len.insert(course[i]);
    for(int i=0;i<orders.size();i++)
        sort(orders[i].begin(),orders[i].end());
    sort(orders.begin(),orders.end());
    for(int i=0;i<orders.size();i++){
        dfs("",orders[i],-1);
    }
    for(auto it = s.begin();it!=s.end();it++){
        string ss = *it;
        int cnt = 0;
        for(int i=0;i<orders.size();i++){
            if(orders[i].size()<ss.size()) continue;
            if(comp(ss,orders[i])) cnt++;
        }
        int l = ss.size();
        if(cnt==1) continue;
        if(v[l].empty()) v[l].push_back({ss,cnt});
        else{
            if(v[l][0].cnt==cnt) v[l].push_back({ss,cnt});
            else if(v[l][0].cnt<cnt){
                v[l].clear();
                v[l].push_back({ss,cnt});
            }
        }
    }
    
    for(auto it = len.begin();it!=len.end();it++){
        int a = *it;
        for(int i=0;i<v[a].size();i++)
            answer.push_back(v[a][i].str);
    }
    sort(answer.begin(),answer.end());
    return answer;
}