Programmers : 메뉴 리뉴얼

문제 링크

풀이요약

조합, 맵

풀이상세

1. 먼저 orders 의 문자열을 정렬하였다. 테스트 케이스 3번의 경우, XWY 등의 문자의 순서가 알맞지 않게 나타는 경우도 있기 때문이다. 정답의 경우가 WX 로 출력이 되기 때문에, 먼저 문자열을 사전순으로 바꾸는 것이 좋다고 판단했다.

2. 현재 문자열의 사이즈가 현재 course 요리의 개수와 동일하거나 큰 경우에만 course 요리의 조합을 나타내는 함수를 실행한다. 나타나는 모든 조합은 맵에 반영한다.

3. 모든 조합을 맵에 반영한 경우, 맵에서 현재 course 요리 가운데 가장 많은 주문 수를 찾는다. 가장 주문이 많은 경우는 반드시 1개라고 보장되지 않기 때문에, 반복문을 통해 현재 course 요리 갯수와 동일하며, 가장 많은 주문 수와 일치하는 요리를 answer에 넣는다.

4. answer를 사전순에 맞게 정렬하여 반환한다.

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string, int> m;
vector<char> tmp;
void comb(int idx, int len, string str) {
    if(str.size() >= len) {
        m[str]++;
        return;
    }
    
    string ss = "";
    for(int i=idx; i<tmp.size(); i++) {
        ss = str + tmp[i];
        comb(i+1, len, ss);
    }
}

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

    for(int i=0; i<orders.size(); i++) {
        // orders[i] 백터에 넣고 정렬
        tmp.clear();
        for(int j=0; j<orders[i].size(); j++) {
            tmp.push_back(orders[i][j]);
        }
        sort(tmp.begin(), tmp.end());
        // course별 조합, map에 추가
        for(auto n : course) {
            if(n <= tmp.size()) comb(0, n, "");
        }
    }   
    for(int i=0; i<course.size(); i++) {
        int cnt = 0;
        for(auto iter = m.begin(); iter!=m.end(); ++iter) {
            if(course[i]==iter->first.size()) cnt = max(cnt, iter->second);
        }

        if(cnt >= 2) {
            for(auto iter = m.begin(); iter!=m.end(); ++iter) {
                if(course[i]==iter->first.size() && iter->second == cnt) {
                    answer.push_back(iter->first);
                }
            }
        }
    }
    // answer 사전 순 정렬 후 출력 
    sort(answer.begin(), answer.end());
    return answer;
}