[Programmers] 프로그래머스 > 메뉴 리뉴얼(c++)

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

코딩테스트 연습 - 메뉴 리뉴얼

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 메뉴 리뉴얼

 

 

식빵맘님의 블로그를 참고해서 조합에 대한 공부 후, 문제 풀이에 적용했다. (링크는 아래쪽에)

 

1. orders의 문자들을 각각 알파벳 오름차순으로 정렬

2. Combination(조합)을 이용해서 course의 수에 해당하는 문자를  menu(=unordered_map)에 추가

3. 각 course당 최댓값을 뽑아서, 최댓값에 해당하는 문자들을 모두 result에 추가

4. result에 있는 문자들의 순서를 알파벳 오름차순으로 정렬

 

 

---

main포함 코드(c++)

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

unordered_map<string, int> menu;
vector<string> result;

void Combination(string arr, vector<char> comb, int index, int depth)
{
    if (depth == comb.size())
    {
        string text = "";
        for(int k=0;k<comb.size();k++)text += comb[k];
        menu[text]++;
        return;
    }
    else
    {
        for(int i = index; i < arr.size(); i++)
        {
            comb[depth] = arr[i];
            Combination(arr, comb, i + 1, depth + 1);
        }
    }
}

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

    for(int i=0;i<orders.size();i++)sort(orders[i].begin(), orders[i].end());
    for(int i=0;i<orders.size();i++){
        for(int j=0;j<course.size();j++){
            if(orders[i].size() < course[j]) continue;
            vector<char> comb(course[j]);
            Combination(orders[i], comb, 0, 0);
        }
    }
    
    for(int i=0; i<course.size(); i++){
        //메뉴에서 first의 길이가 2인것중에 최댓값, 3인것중에 최댓값, 4인것 중에 최댓값
        int Max = 0;
        for(auto iter : menu ){
            if(iter.first.size() == course[i]) Max = max(Max, iter.second);
        }
        
        for(auto iter : menu ){
            if(iter.second == Max && iter.first.size() == course[i] && Max >= 2) result.push_back(iter.first);
        }
    }
    sort(result.begin(), result.end());
    return result;
}
int main()
{
    vector<string> orders = {"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"};
    vector<int> course = {2,3,4};
 
//    vector<string> orders = {"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"};
//    vector<int> course = {2,3,5};
    
//    vector<string> orders = {"XYZ", "XWY", "WXA"};
//    vector<int> course = {2,3,4};
 
    solution(orders, course);
    
    return 0;
}

 

어떻게 풀어야하는지 감이 잘 잡히지 않아서 질문게시판을 참고해서 조합을 해서 풀면 된다는 걸 깨달은 후 접근했다.

솔루션을 생각하는 힘이 아직 많이 부족한 것 같다. 모르면 바로 검색하는 것 보다 혼자 좀더 생각해봐야겠다. ㅠㅠ

2시간은 넘게 걸린것 같다,,ㅠㅠ

---

참고한 블로그

https://ansohxxn.github.io/algorithm/combination/