[Programmers] 메뉴 리뉴얼(Lv.2)

풀이 소요시간 : 측정 안함(컨디션 난조)

일단 스스로 푸는데는 성공했다. 문제를 집중해서 안읽는 바람에 시간을 소모했다. 백트래킹 구현에서도 실수가 있었다. 하지만 문자열 조합으로 해시를 구현하는 문제의 핵심 은 빠르게 파악했다. 문제를 잘못 이해해서 그렇지 구현상 어려운 부분은 없었는데 시간을 너무 많이 써서 현타가 온다.

전체 코드

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

string Curr;
unordered_map<string, int> Map;

bool Cmp(pair<int, string> A, pair<int, string> B) {
    if(A.first == B.first)
    {
        return A.second > B.second;
    } 
    return A.first > B.first;
}


void Dfs(int Count, int Index, string Str, int Goal) {
    
    if(Count == Goal)
    {
        Map[Str]++;
        return;
    }
    
    //오름차순 & 중복 알파벳 제거
    for(int i = Index; i < Curr.length(); i++)
    {
        Dfs(Count + 1, i + 1, Str + Curr[i], Goal);
    }
    
}


vector<string> solution(vector<string> orders, vector<int> course) {
    
    vector<string> Ans;
    
    for(string s : orders)
    {
        Curr = s;
        sort(Curr.begin(), Curr.end());
        //문자열 알파벳 순으로 정렬
        
        for(int i = 1; i <= Curr.length(); i++)
        {
            Dfs(0, 0, "", i);
        }
    }
    
    
    
    //[2, 3, 4]
    for(int Goal : course)
    {
        vector<pair<int, string>> Temp;
        
        for(auto E : Map)
        {
            //주문 2명 이상 & 메뉴 Goal 개
            if(E.second >= 2 && E.first.length() == Goal)
            {
                Temp.push_back({E.second, E.first});
            }
        }
        
        //주문건 기준 내림차순
        sort(Temp.begin(), Temp.end(), Cmp);
        
        
        //최대 주문 코스 삽입(복수 가능)
        int Max = Temp[0].first;
        for(auto E : Temp)
        {
            if(Max == E.first) Ans.push_back(E.second);
            else break;
        }
        
    }
    
    
    sort(Ans.begin(), Ans.end());
    return Ans;
    
}