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

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

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

 

 

 

[난이도] level2
[유형] 구현

[풀이]
순수 구현 문제입니다.
모든 order를 정렬 뒤에 순회하면서 비트마스크를 이용해
모든 요리 코스 조합이 몇개 존재하는지 map에 저장하였습니다.
mp["코스"]=등장한 개수 (mp["AB"]=2) 와 같이 저장됩니다.

그 뒤 courses 배열을 순회하면서
코스에 포함된 요리 개수가 courses[i] 이면서 등장한 코스의 개수가 2개 이상인 것들을
vector에 <등장한 개수,"코스"> 형식으로 저장 한 뒤 오름차순으로 정렬합니다.

vector에서 등장한 개수가 큰 코스들은 answer vector에 저장해주면 됩니다.

모든 courses를 확인 후

answer를 정렬해주면 최종 정답입니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <cstdio>
using namespace std;
map<string,int> mp;

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

    for(auto& order : orders){
        sort(order.begin(),order.end());

        int sz = order.size();
        for(int i=0;i<(1<<sz);i++){

            vector<bool> flag(sz);
            string tmp;
            for(int j=0;j<sz;j++){
                if((i&(1<<j))>0) flag[j]=1;         
            }
            for(int j=0;j<sz;j++){
                if(flag[j]) tmp.push_back(order[j]);
            }
            if(tmp.size()>=2) {
                mp[tmp]++;
            }
        }
    }
    for(auto c : course){
        vector<pair<int,string>> v;
        for(auto& p : mp){
            if(p.first.size()==c && p.second>=2){
               v.push_back({-p.second,p.first});   
            }
        }
        if(v.empty()) continue;
        sort(v.begin(),v.end());

        int minV = v[0].first;
        for(auto& p : v){
            if(minV!=p.first) break;
            answer.push_back(p.second);
        }
    }
    sort(answer.begin(),answer.end());

    return answer;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/메뉴 리뉴얼.cpp