2021) 카카오 - 메뉴 리뉴얼

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<string, int> string_cnt_map; //str의 주문횟수는 n
int cnt[27]; //길이가 n인 메뉴의 현재 최대 주문횟수
vector <string> menu[27][21]; //길이가 i이고, j번 주문된 것들의 목록
//같은 길이의 메뉴가 여러것일 것에 대비, i만큼의 사이즈를 지닌 것에 대해 총 21개를 넣을 수 있도록

void comb(string s, string made, int idx){
    //사이즈가 2 이상일 떄
    if(made.size() > 1) {
        string_cnt_map[made] ++;
        //made의 주문횟수를 1 증가시키고, 기존 해당 size의 주문횟수와 새로 추가된
        //made만큼의 사이즈를 비교해 갱신
        cnt[made.size()] = max(cnt[made.size()], string_cnt_map[made]);
        menu[made.size()][string_cnt_map[made]].push_back(made);
        //made의 size만큼: i, 이중 made의 주문횟수:j에, made 삽입
    }

    //made에, s[i]를 넣고 다시 돌린다.
    //다 빠져나와 pop_back을 실행하는 경우는 idx+1 == s.size()인 경우
    //이땐, 이전 것으로 돌아와 pop을 하고 다음 idx의 element를 넣어 재시작
    for(int i=idx+1; i<s.size(); i++) {
        made.push_back(s[i]);
        comb(s, made, i);
        made.pop_back();
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    for(string& str : orders) {
        sort(str.begin(), str.end());
        comb(str, "", -1);
    }

    for(int i:course)
        if(cnt[i]>1) // 길이가 i인 조합의 최대 주문 횟수가 1 이상인 경우만
            for(string s:menu[i][cnt[i]])
                answer.push_back(s);

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

    return answer;
}

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

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

이분거 보고 한 번 쓰면서 알고리즘 이해한 후 복기하며 했는데 거의 복붙수준으로 나왔다. 

이번엔 어거지로 푼거나 다름없으니 몇 달 뒤에 머리 완전히 비게 된 다음에 다시 풀어야겠다.