Programmers Level2: 메뉴 리뉴얼

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

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

풀이법

1) Map 자료형과 조합(Combination)을 이용한 구현 문제이다.

2) map<string,int> 자료형에 몇 번의 해당 값이 나왔는지를 확인할 수 있도록 하고 course 배열 안의 값에 따라 이를 확인하여 result를 만드는 과정이 중요한 부분이었다.

                string s = orders[j];
                sort(s.begin(), s.end());
                vector<int> ind;
                for (int k = 0; k < num; k++)
                    ind.push_back(1);
                for (int k = 0; k < s.size() - num; k++)
                    ind.push_back(0);
                sort(ind.begin(), ind.end());
                do {
                    string temp;
                    for (int k = 0; k < ind.size(); k++) {
                        if (ind[k] == 1) {
                            temp.push_back(s[k]);
                        }
                    }
                    m[temp]++;

                } while (next_permutation(ind.begin(), ind.end()));

 

next_permutation을 활용하여 조합을 만드는 부분이 이 문제에서 가장 중요한 부분이다.

제대로 된 조합을 만들기 위해서 sort 알고리즘을 이용하여 정렬하였고, 

뽑아야 하는 string의 크기 만큼 1을 나머지를 0으로 채워진 배열을 만들어 이를 활용하여

조합을 생성하였다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0; i<course.size();i++)
    {
        int num=course[i];
        map<string,int> m;
        for(int j=0; j<orders.size();j++)
        {
            if(orders[j].size()>=num)
            {
                string s = orders[j];
                sort(s.begin(), s.end());
                vector<int> ind;
                for (int k = 0; k < num; k++)
                    ind.push_back(1);
                for (int k = 0; k < s.size() - num; k++)
                    ind.push_back(0);
                sort(ind.begin(), ind.end());
                do {
                    string temp;
                    for (int k = 0; k < ind.size(); k++) {
                        if (ind[k] == 1) {
                            temp.push_back(s[k]);
                        }
                    }
                    m[temp]++;

                } while (next_permutation(ind.begin(), ind.end()));
            }
        }
        int c=0;
        for(auto a=m.begin();a!=m.end();a++)
        {
            if(c<a->second)
            {
                c=a->second;
            }
        }
        for(auto a=m.begin();a!=m.end();a++)
        {
            if(c==a->second)
            {
                if(c==1)
                    continue;
                answer.push_back(a->first);
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}