프로그래머스 - 메뉴 리뉴얼

프로그래머스 - 메뉴 리뉴얼

문제가 잘 이해가 안되서 몇번 읽어본 것 같다.

구현 핵심은 크게 다음과 같다.
1. orders에 대해서 course의 combination을 구해야함

• course : [2, 3, 4]라고 가정하면 orders 벡터의 각 문자열에 대해서 2개의 문자를 뽑는 경우, 3개의 문자를 뽑는 경우, 4개의 문자를 뽑는 경우를 모두 구해야한다.
• 이 때, XA와 AX는 같은 것으로 중복으로 취급해야 한다. 이를 위해 orders의 문자열을 미리 sort시켜준다. 즉, ABCDE와 같은 형태로 만들어주고, 조합을 만들 때 앞에서부터 뽑는다면 다 뽑은 뒤 중복을 따로 체크안해도 된다.

2. 뽑아진 조합의 중복을 없애서 unique 조합으로 만들어준다.

• 예를 들어 orders : [ABC, AB], course : [2] 라면, [AB, AC, BC, AB]가 조합으로 나오게 되는데, 이를 [AB, AC, BC]로 취급해줘야 한다. 이를 위해 unordered_set을 사용한다.

3. unique 조합에 대해서 orders의 각 문자열들이 포함하고있는지 여부를 체크하고, 만약 2개 이상의 문자열이 포함하고 있다면 정답 후보군이다.

• 위 예시의 unique 조합의 AB는 orders의 ABC, AB에서 포함하고 있기 때문에 정답 후보군이 될 수 있다.

4. 만약 정답 후보군이 여러개면 모두 정답이 된다.

• 예를 들어, orders : ["XYZ", "XWY", "WXA"], course : [2,3,4]의 WX, XY는 course : [2]일 때의 결과이고, 이 둘은 orders의 두 문자열에 포함된다. 따라서 이 둘은 모두 정답이다.
• 이를 위해 정답 후보군들이 생길 때마다 몇개의 문자열에 포함되었는지에 대해 max값을 구해 놓는다. 그 후 정답 후보군을 순회하면서 포함된 문자열의 갯수가 max값과 같은 것만 정답에 넣어주면 된다.

5. 정답을 sort해준다.

코드는 아래와 같다.

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

using namespace std;

int visit[26];
vector<char> result;
vector<string> ans;
void combination(int n, int depth, int start, const string &orders)
{
    if(depth == n) {
        string str(depth, 0);
        for(int i=0;i<depth;i++) 
            str[i] = result[i];
        ans.push_back(str);
        return;
    }
    
    for(int i=start;i<orders.size();i++) {
        if(visit[i] == 1)
            continue;
        visit[i] = 1;
        result[depth] = orders[i];
        combination(n, depth + 1, i, orders);
        visit[i] = 0;
    }
    return;
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    result.assign(11, 0);
    
    for(int i=0;i<course.size();i++) {
        map<string, int> already;
        for(int j=0;j<orders.size();j++) {
            sort(orders[j].begin(), orders[j].end());
            if(already[orders[j]] == 1)
                continue;
            already[orders[j]] = 1;
            if(course[i] < orders[j].size()) 
                combination(course[i], 0, 0, orders[j]);
            else if(course[i] == orders[j].size())     
                ans.push_back(orders[j]);
        }
        
        unordered_set<string> u(ans.begin(), ans.end());
        map<string, int> m;
        for(auto it : u) 
            m[it] = 0;
        
        int max_len = 0;
        for(auto it : m) {
            int map[26] = { 0, };
            for(int j=0;j<it.first.size();j++) 
                map[it.first[j] - 'A'] = 1;
            
            int cnt = 0;
            for(int j=0;j<orders.size();j++) {
                if(orders[j].size() < it.first.size())
                    continue;
                int tmp = 0;
                for(int k=0;k<orders[j].size();k++) 
                    if(map[orders[j][k] - 'A'] == 1) {
                        tmp++;
                        if(tmp == it.first.size()) {
                            cnt++;
                            break;
                        }
                    }
            }
            if(cnt > 1) {
                m[it.first] += cnt;
                max_len = max(m[it.first], max_len);
            }
        }
        if(max_len == 0)
            continue;
        
        vector<string> tmp;
        for(auto it : m) 
            if(it.second == max_len)
                tmp.push_back(it.first);
        
        for(auto it : tmp) 
            answer.push_back(it);
        
        ans.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}