[프로그래머스] 메뉴 리뉴얼 (c++) map, 조합

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

프로그래머스

풀이 방법

order, orders의 크기가 작으므로 완전탐색 + 조합의 문제인 것을 확인할 수 있다.

 

이제 조합을 어떻게 구현할지에 대해 생각을 해보아야 한다.

 

course마다 돌아가며 모든 조합을 딕셔너리에 보관하는 방법으로 풀이했다.

 

여기서 중요한 점은 map의 초기값은 자동으로 0으로 할당이 된다는 것이다.

 

즉 combination [temp]++ 를 수행하기 위해 temp키 값이 초기화되어 있으면 +1, 초기화 되어 있지 않으면 초기화 후 +1을 하는 과정이 없어도 된다는 것이다.

 

이후 과정은 dfs를 통해 문자를 하나씩 추가하며 원하는 길이가 되었을 때, map에 추가해 주면 된다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

map<string, int> combination;

// 비교 함수 (사용하지 않으셔도 무방)
bool cmp(pair<string, int> &a, pair<string, int> &b) {
    return a.second > b.second;
}

// 각 order에 대해 조합의 수가 len인 단품메뉴 조합의 주문 개수 카운트
void dfs(string &order, int &len, string tmp, int idx) {
    if (tmp.length() == len) {
        combination[tmp]++; // 해당 조합의 주문 수++, 초기 값은 0으로 설정이 된다. 
        return;
    }
    
    for (int i = idx; i < order.length(); i++) {
        dfs(order, len, tmp + order[i], i + 1);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
        
    for (int i = 0; i < course.size(); i++) {
        int len = course[i];
            
        for (int j = 0; j < orders.size(); j++) {
            string order = orders[j];
            sort(order.begin(), order.end());
            dfs(order, len, "", 0);
        }
        
        int maxCount = 0; // 가장 많이 주문된 수
                
        for (auto it: combination) {
            maxCount = max(maxCount, it.second);
        }

        for (auto it: combination) {
            if (maxCount < 2) break;
            else if (combination[it.first] == maxCount) answer.push_back(it.first);
        }                
        
        // 다음 단품메뉴의 개수(len)에 대한 연산을 위해 초기화
        combination.clear();
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}