[프로그래머스] Level 2. 메뉴 리뉴얼

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

 

해결 방법

• 가능한 조합을 모두 찾고, unordered_map 에 ("abc",3개) 처럼 등장한 개수를 모두 저장한다.
• 조합중에 개수가 가장많은것을 찾고, 그 조합을 answer에 넣는다.

해결방법은 매우 간단한데, 가능한 조합을 어떻게 모두 찾을것인가? 

재귀를 이용하여 풀었다. 실무에서는 재귀를 거의 안썼던것같은데 알고리즘 문제에서는 재귀가 꽤 많이 사용되는 듯 하다.

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


void combination(unordered_map<string,int>& m , string src, string dist ,int k ){
    if(dist.size() == k){
        m[dist] +=1;
        return;
    }
    
    if(src.size() <=0) return;
    
    for(int i=0 ; i< src.size(); i++){
        combination(m,src.substr(i+1),dist+src[i],k);
    }    
}


vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    unordered_map<string,int> m;
    
    for(int i=0; i<course.size(); i++){  //모든 코스개수에 반복
        
        m.clear();
        for(int j=0; j<orders.size(); j++){
            sort(orders[j].begin(), orders[j].end());
            combination(m,orders[j],"",course[i]); //모든 조합을 찾음.
        }
        
        int max= 0; //최대개수를 찾음.
        for(const auto& item : m){
            if(item.second >=2 && max < item.second) max = item.second;
        }
    
        if(max <= 0) continue; //조합없음.
        for(const auto& item : m){
            if(max == item.second) answer.push_back(item.first);
        }    
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}