C++ / 프로그래머스 / 메뉴 리뉴얼

문제

 

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

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

 

 

문제풀이

 

메뉴의 부분집합들을 구하면서 해당 메뉴가 몇 번 나왔는지를 구해야 한다.

그다음 길이가 같은 메뉴가 여러 개가 있다면 가장 많이 나온 메뉴만 answer에 입력해야 한다.

 

CanMenu라는 bool형 벡터를 선언하여 course 벡터를 탐색하면서 코스요리로 만들 수 있는 메뉴의 개수에 해당하는 부분을 true로 바꾼다.

 

그다음 부분집합을 구한다.

부분집합은 DFS 또는 비트마스크로 구할 수 있는데 이번 문제에서는 비트마스크로 구했다.

    for (int idx = 0; idx < orders.size(); ++idx) {
        for (int i = 1; i < (1 << orders[idx].size()); ++i) {
            string menu("");
            for (int j = 0; j < orders[idx].size(); ++j) {
                if (i & (1 << j)) menu += orders[idx][j];
            }
            sort(menu.begin(), menu.end());
            if (CanMenu[menu.size()] == true) {
                ++menu_list[menu];
            }
        }
    }

비트마스크로 메뉴의 부분집합들을 구하는 과정이다.

예제 3번을 보면 "XWY", "WXA"의 메뉴들로 "WX"라는 코스요리를 만들 수 있다.

따라서 부분집합들을 구할 때 sort를 이용하여 메뉴의 순서를 정렬하였다.

그리고 부분집합의 크기가 CanMenu라는 벡터를 통해 true값인지 판별을 한다.

 

    vector<psi>menu_info(menu_list.begin(), menu_list.end());
    sort(menu_info.begin(), menu_info.end(), cmp);
    vector<int>cnt(11, 0);

위 과정이 종료되었으면 해당 메뉴 구성이 몇 번 나왔는지가 unoredered_map인 menu_list에 저장되었을 것이다.

그다음은 코스요리로 만들 수 있는지 확인을 하는 과정이다.

메뉴가 2명 이상의 사람에게 나와야 하고 길이가 같은 메뉴가 여러 개 있다면 가장 많이 나온 횟수의 메뉴들만 코스요리로 만들 수 있다.

 

unordered_map을 key가 아닌 value 기준으로 정렬을 해야 하므로 vector에 복사하여 sort를 이용해 정렬한다.

cnt는 cnt[메뉴 길이] = 메뉴가 나온 횟수로 정의한다.

 

    for (int idx = 0; idx < menu_info.size(); ++idx) {
        string menu_name = menu_info[idx].first;
        int menu_cnt = menu_info[idx].second;
        int menu_len = menu_name.size();

        if (menu_cnt == 1) continue;
        if (cnt[menu_len] == 0 || cnt[menu_len]== menu_cnt) {
            cnt[menu_len] = menu_cnt;
            answer.push_back(menu_name);
        }        
    }

menu_info 벡터를 탐색하면서 한 번만 나온 메뉴는 continue를 통해 넘긴다.

그 외에는 가장 많이 나온 메뉴들일 때만 answer에 push_back 하도록 한다.

 

마지막으로 answer을 오름차순으로 정렬하고 return 하면 된다.

 

 

 

코드

#include <unordered_map>
#include <algorithm>
#include <string>
#include <vector>
#define psi pair<string, int>
using namespace std;

bool cmp(pair<string, int>& p1, pair<string, int>& p2) {
    return p1.second > p2.second;
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    vector<bool>CanMenu(11, false);
    unordered_map<string, int>menu_list;
    for (int idx = 0; idx < course.size(); ++idx) {
        CanMenu[course[idx]] = true;
    }

    for (int idx = 0; idx < orders.size(); ++idx) {
        for (int i = 1; i < (1 << orders[idx].size()); ++i) {
            string menu("");
            for (int j = 0; j < orders[idx].size(); ++j) {
                if (i & (1 << j)) menu += orders[idx][j];
            }
            sort(menu.begin(), menu.end());
            if (CanMenu[menu.size()] == true) {
                ++menu_list[menu];
            }
        }
    }

    vector<psi>menu_info(menu_list.begin(), menu_list.end());
    sort(menu_info.begin(), menu_info.end(), cmp);
    vector<int>cnt(11, 0);

    for (int idx = 0; idx < menu_info.size(); ++idx) {
        string menu_name = menu_info[idx].first;
        int menu_cnt = menu_info[idx].second;
        int menu_len = menu_name.size();

        if (menu_cnt == 1) continue;
        if (cnt[menu_len] == 0 || cnt[menu_len]== menu_cnt) {
            cnt[menu_len] = menu_cnt;
            answer.push_back(menu_name);
        }        
    }

    sort(answer.begin(), answer.end());
    return answer;
}