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

교공 알고리즘 스터디 26주차 카카오기출

메뉴 리뉴얼 | 문제 바로가기

문제풀이 (2022-03-08 TUE 💻) & 스터디 (2022-03-13 SUN 📚)

🤔 사담

개인적으로 아래의 풀이의 핵심에서
unordered_map을 써야겠다는 생각은 떠올리지 못해서
구글링의 도움을 좀 받았다..
문자열이 나오는 문제를 보면 좀.. 당황 + 사고 회로가 멈추는 것 같다..
문자열 많이 나오는 카카오 기출 좀 열심히 풀어야겠다

⭐ 풀이의 핵심

조합과 unordered_map을 쓰는 게 핵심이었다
입력 조건을 보면 브루트포스가 가능하다는 느낌이 빡.. 오는 문제이다
아래와 같은 흐름으로 구현할 수 있다

• orders[i] 에서 가능한 메뉴 구성 후보를 모두 찾아내어 (조합, next_permutation 활용)
• 메뉴 구성 후보 별로 나온 횟수를 저장하고 (unordered_map 활용)
• 횟수가 많은 순으로 후보를 정렬한 후
• 구성하는 단품메뉴 개수가 courses[i]이고 2명 이상의 손님으로부터 주문된 후보 중 가장 많은 손님을부터 주문된 후보를 answer에 담는다
• answer를 오름차순으로 정렬하여 반환한다

🔽 코드 (C++)

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

unordered_map<string, int> m;

bool cmp(const pair<string, int> &a, const pair<string, int> &b) {
    return a.second > b.second;
}

void getCombination(string order, int count) {
    // next_permutation을 활용한 조합 구하기
    vector<int> selected;
    for (int i=0; i<order.size()-count; i++) { selected.push_back(0); }
    for (int i=0; i<count; i++) { selected.push_back(1); }
    
    do {
        string key = "";
        for (int i=0; i<selected.size(); i++) {
            if (selected[i]) { key += order[i]; }
        }

        // cf) 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬
        sort(key.begin(), key.end()); 
        m[key]++;
    } while (next_permutation(selected.begin(), selected.end()));
}

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

    for (int i=0; i<orders.size(); i++) {
        for (int j=0; j<course.size(); j++) {
            if (orders[i].size() >= course[j]) {
                getCombination(orders[i], course[j]);
            }
        }
    }

    // 주문된 횟수가 많은 순으로 단품메뉴 조합 정렬
    vector<pair<string, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp); 

    for (int i=0; i<course.size(); i++) {
        int maxCount = 2;
        for (auto iter=v.begin(); iter!=v.end(); iter++) {
            if (iter->first.size() == course[i] && iter->second >= maxCount) {
                maxCount = iter->second;
                answer.push_back(iter->first);
            }
        }
    }

    // cf) 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬
    sort(answer.begin(), answer.end()); 

    return answer;
}