[C++] 프로그래머스 : 메뉴 리뉴얼

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

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

 

단순히 조합을 구하는 것이 아닌, 주어진 변수에서 여러가지 원하는 형태로 조합을 구해 답을 내야했던 문제

next_permutation에 대해서도 정확히 알게되었는데,

next_permutation 파라미터로 준 문자열을 처음부터 조합을 주는게 아닌

비교함수에 따라 주어진 문자열 상태부터 마지막 조합까지이다.

예를 들어 디플토비교함수(오름차순)일 때 다음과 같은 문자열을 주고 동작시키면

 

1) 0011 : 0011, 0101, 0110, 1001, ... 1100 끝

2) 1100 : 1100 끝

 

처럼 2) 경우 처음부터 오름차순 마지막 조합의 경우를 주었기 때문에 do while 문은 한번 반복된 후 종료된다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i=0; i<orders.size(); i++){
        sort(orders[i].begin(), orders[i].end());
    }
    
    for(int i=0; i<course.size(); i++){
        int cosLen = course[i];
        map<string, int> m;
        
        for(int j=0; j<orders.size(); j++){
            if(orders[j].length() < cosLen)
                continue;
            
            string curOrd = orders[j];
            int ordLen = orders[j].length();
            
            string mask = "";
            for(int k=0; k<cosLen; k++)
                mask += "0";
            for(int k=cosLen; k<ordLen; k++)
                mask += "1";
            
            do{
                string tmp = "";
                for(int k=0; k<ordLen; k++){
                    if(mask[k]=='0')
                        tmp+=curOrd[k];
                }
                m[tmp]++;
            }while(next_permutation(mask.begin(), mask.end()));
        }
        
        int maxCnt = 1;
        for(auto cm : m){
            maxCnt = maxCnt<cm.second?cm.second:maxCnt;
        }
        if(maxCnt==1) continue;
        for(auto cm : m){
            if(cm.second == maxCnt)
                answer.push_back(cm.first);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}