프로그래머스 메뉴리뉴얼 c++ // 비트마스킹 조합

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

프로그래머스

1. 시행착오

a~y 모든 조합을 돌리고 하는방법 X

결론 : DB설정을 잘해서 저장하자.

freq[size][문자열] = 등장횟수

 

2. 비트 -> 문자열 만드는법

비트가켜져있는경우 해당 문자를 더하면된다.

if(subset & (1<<i)) -> str+=order[j]하면된다.

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

map<string,int> freq[11]; 
//freq[2][AB]=3 : size가 2인 , AB의 등장횟수는 3번
//freq[2][XY]=7 : size가 2인 , XY의 등장횟수는 7번

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    map<string, int> m; //코스이름, 등장횟수
    
    //코스메뉴 조합추출
    /*
        j :  0 1 2 3 4
    order -> A B C F G
    subset : 1 0 0 0 0
             0 1 0 0 0
             ...
             1 1 0 0 0
             ...
    */
    for(auto order : orders){ //ABCFG
        sort(order.begin(),order.end());
        for(int subset=1;subset<(1<<order.size());++subset){ // A, AB, ABC, ...
            string menu;
            for(int j=0;j<order.size();++j){
                if(subset & (1<<j)) menu+=order[j]; 
                //비트가켜져있는 해당메뉴저장
                //ex : 11000 -> AB
            }
            //freq[2][AB]++;
            freq[menu.size()][menu]++;
        }
    }
    
    //코스요리 메뉴 계산
    //freq[2][AB]=3 : size가 2인 , AB의 등장횟수는 3번
    //freq[2][XY]=7 : size가 2인 , XY의 등장횟수는 7번

    vector<string> ans;
    for(auto i : course){
        int mxfreq=0;
        for(auto p : freq[i]) //해당길이의 map에 대해 최대값찾기
            mxfreq=max(mxfreq,p.second);
        if(mxfreq<2) continue;
        for(auto p : freq[i]){ //최대값인 메뉴들 정답에 담기
            if(p.second==mxfreq) ans.push_back(p.first);
        }
    }

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