프로그래머스 카카오, 메뉴 리뉴얼 C++ [CPP] ★★★★★

MAP을 쓰는 정말 좋은 문제가 아닐까 싶다.

처음 생각하기는 어렵다.

하지만.. 알고 나면 너무나 쉽다.

 

 

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;
    
//orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열 => 음식을 10개 초과로 시킬 수 없음
unordered_map<string, int> combination[11]; // "음식이름", "횟수"
//index는 음식의 수를 말함 combination[3] => 3가지로 만들 수 있는 조합

int mxCount[11]; //해당 조합 중에서 가장 많이 중복된 값


void comb(string str, int cnt, string result){
    if(cnt == str.size()){
        //num => 메뉴 개수
        int num = result.size();
        //result => 메뉴 조합
        combination[num][result]++;
        //최대인지 확인
        mxCount[num] = max(mxCount[num], combination[num][result]);
        return;
    }
    
    //조합 ★★★★★
    //해당 문자 선택함
    comb(str, cnt + 1, result + str[cnt]);
    //해당 문자 선택하지 않음
    comb(str, cnt + 1, result);

}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(auto order : orders){
        //조합 만들 때도 오름차순으로 만들어야함.
        sort(order.begin(), order.end());
        comb(order, 0, "");
    }
    
    //course에 맞는 것들 뽑아서 넣음
    // 2명 이상의 손님이 시켜야함.
    for(auto num : course){
        for(auto x : combination[num]){
            if(x.second == mxCount[num] && x.second >= 2){
                answer.push_back(x.first);
            }
        }
    }
    
    // 결과도 오름차순 정렬
    sort(answer.begin(), answer.end());
    return answer;
}

 

 

처음에 구조 잡는게 어렵다.

어떻게 MAP을 이용해야하지??

결국 AG, EG, GFH처럼 문자열의 Count를 세는 것이구나..? 그 메뉴는 유일하고..? 그럼 Map을 써도 되지 않을까?

Count하는데 <string, int>만한게.. 없지 하면서

그냥 했다.

 

그 다음 여러가지 조건이 붙는데 2명 이상의 손님이 주문했어야 했다.

그리고 가장 많이 주문한 메뉴를 알아야 했다.

즉, 2명 이상이면서 가장 많은 주문 수를 알아야 했기에

해당 메뉴 개수의 최대 주문 수를 저장해야 했고, 해당 메뉴가 2명 이상에게 주문되었는지도 체크해야 했다.

 

문제를 잘 읽으면 답이 나온다지만.. 잘 읽는 것만으로는 솔직히 충분하지 않다.

내가 왜 Count를 할 때 Map을 생각했는지 이 문제를 풀어보고 느끼길 바란다.