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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 2021 KAKAO BLIND RECRUITMENT 문제였습니다.

글쓴이는 DFS로 풀이했습니다.

 

 

 

 

📝 문제 풀이

1. orders 벡터의 각 단품메뉴에 대해서 course 요소만큼의 코스요리의 메뉴 구성의 주문 횟수를 dfs를 통해 combination 맵에 누적 ⭐️

2. combination 맵에서 가장 많이 주문된 수를 maxCount 변수에 저장

3. maxCount가 2보다 크다면, combination 맵에서 maxCount와 같은 값을 가진 키를 answer 벡터에 삽입

4. for문이 종료된 후 answer 벡터 오름차순 정렬

 

 

 

 

 

👩🏻‍💻 C++ 코드

#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]++; // 해당 조합의 주문 수++
        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 len: course) {
        for (string order: orders) {
            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);
        }
        
        combination.clear(); // 다음 단품메뉴의 개수의 연산을 위해 clear
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

 

프로그래머스 - 결과 화면