[프로그래머스] 메뉴 리뉴얼 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 메뉴 리뉴얼 문제이다.

 

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

 

course별로 가장 많이 불린 조합들을 반환하는 문제입니다. 가장 많이 불린 횟수가 중복될 경우 중복 모두 반환합니다.

 

 

해결 과정

 

총 메뉴는 10개까지 시킬 수 있음으로 크기 11개의 해쉬테이블을 생성하고 각 손님들의 주문 속 메뉴들의 모든 조합을 구하여 조합의 갯수 별로 저장을 합니다. 각 조합들의 길이 당 가장 많이 주문된 횟수를 저장할 배열을 11개의 크기로 생성해

저장합니다. 이제 각 주문별로 조합을 구하며 중복된 조합이 나올 경우 해당 조합의 수를 올려줍니다. 그리고 중복된 조합의 주문된 횟수가 현재 조합의 길이의 가장 많이 주문된 횟수보다 크다면 대체합니다.

이렇게 조합과 불려진 횟수와 최대 불려진 횟수를 구한 뒤 course별로 해쉬테이블을 가져와 각 조합들의 불려진 횟수가

가장 많이 주문된 횟수와 동일하다면 반환배열에 저장합니다.

이후 반환배열을 정렬하고 이름 반환합니다.

 

 

 

 

코드 전문

 

 

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

using namespace std;

unordered_map<string, int> food_map[11]; // 다중 해시
vector<int> max_food_cnt (11, 0); 

void dfs(string& order_menu, int pos, string temp_str)
{
    if (pos >= order_menu.size())
    {
        int len = temp_str.size();
        if (len >= 2) 
        {
            sort(temp_str.begin(), temp_str.end());
            food_map[len][temp_str]++;
            max_food_cnt[len] = max(max_food_cnt[len],food_map[len][temp_str]); // max in algorithm lib
        }
        return;
    }
    dfs(order_menu, pos+1, temp_str + order_menu[pos]);
    dfs(order_menu, pos+1, temp_str);
}



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

    
    for (auto str : orders)
    {
        dfs(str, 0, "");
    }
    for (auto len : course)
    {
        for (auto item : food_map[len])
        {
            if (item.second >= 2 && item.second == max_food_cnt[len])
                answer.emplace_back(item.first);
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

으어... 문제 이해가 안돼서 정말 고생했습니다. 조합을 구하기 위해 STL의 제공함수이며 순열을 구하는 

next_permutation 함수를 사용하였는데, 코드가 너무 복잡해져 DFS로 조합을 구하였습니다.

이후 시간이 너무 소모되자 유튜브 선생님께 물어봤습니다. 

다중해쉬맵을 저렇게 사용할 수도 있는 군요. unordered_map< , > asd[10]; 제 머리만 싸메고 문제를 해결하기 보다는 가끔씩은 고수분들의 코드를 보면서도 많을 걸 배울 수 있네요. 끈기를 가지고 문제에 도전하는 것도 좋지만

자존심을 버리고 수용하는 것도 중요해보입니다.잘하시는 분들은 정말 잘 하시네요. 정말 체계적이고

정의된 동작에 배울게 많에요.

 

 

 

 

 

다음 영상을 참조하였습니다. 감사합니다.

https://www.youtube.com/watch?v=iTS0KdaEYi8

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.