[PG/C++] 프로그래머스 Lv2 - 메뉴 리뉴얼

🐹 문제 설명

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

프로그래머스

😊 해결 과정

1. 주문된 모든 메뉴 조합 orders에 대해서, 코스요리 메뉴로 선정 가능한 후보를 모두 뽑는다.

void findCombination(string order, int index, string& result, set<set<char>>& combinations) {
    if (index == order.size()) {
        if (result.size() >= 2){
            set<char> s;
            for(char c : result)
                s.insert(c); 
            combinations.insert(s); 
        }
        return;
    }
    result.push_back(order[index]);
    findCombination(order, index + 1, result, combinations);
    result.pop_back();
    findCombination(order, index + 1, result, combinations);
}


 set<set<char>> combinations;
    for (string order : orders) {
        string result; 
        findCombination(order, 0, result, combinations);
}

이는 Brute-Force 방식으로 조합을 구하였고, 메뉴의 최대 개수는 10개이기 때문에 시간 복잡도는 O(2*10)이 된다.

이 때, 만들어진 코스 요리 조합에 있는 메뉴의 개수가 2개 이상일 때만 조합에 추가한다. 코스 요리의 메뉴는 최소 2개여야 하기 때문이다.

여기서 set<set<char>> 과 같은 자료구조를 사용하여 조합을 저장한 이유는, 여러 조합이 중복되어서 저장할 수 없으며 메뉴의 순서를 신경쓰지 않기 위함이다.

 

2. 각 조합이 주문된 횟수를 계산한다.

    // 각 조합이 주문된 횟수를 구한다. 
    map<set<char>, int> mp;
    for (auto& p : mp)
        p.second = 0;

    for (auto combi : combinations) {
        for (string order : orders) {
            bool flag = true;
            for(char c : combi){
                if(order.find(c) == string::npos) {
                    flag = false; 
                    break;
                }
            }
            if(flag) mp[combi]++;
        }
    }

구한 combinations 집합을 모든 orders와 비교해서, 코스요리 조합의 후보를 시킨 주문의 개수를 계산해주었다.

 

3. 주문 횟수를 구하였으니, 최소 2명 이상의 손님으로부터 주문된 조합이고 만들고자 하는 메뉴 개수에 해당하는 것 중 가장 많이 주문된 조합을 찾아 answer 배열에 넣는다.

   // 각 조합이 등장한 횟수의 최댓값을 구한다.
    vector<string> answer;
    for(int x : course){
        int max = 0;
        vector<string> tmp; 
        cout << "x : " << x << endl;
        for (const auto& p : mp) {
            if (p.first.size() == x) {
                if (p.second > max) {
                    max = p.second;
                    tmp.clear();
                    if(mp[p.first] >= 2)
                        tmp.push_back(make_string(p.first));
                }
                else if (p.second == max){
                     if(mp[p.first] >= 2)
                        tmp.push_back(make_string(p.first));
                }
            }
        }

        for(string s : tmp)
            answer.push_back(s);
    }
    sort(answer.begin(), answer.end());

course 배열에 만들고자 하는 조합의 개수가 담겨있다. 따라서 모든 조합을 탐색하면서, 메뉴의 개수가 요구된 개수 (x)와 일치하면서 2명 이상에게 선택 받은 가장 큰 조합을 찾아 tmp 배열에 담는다.

문제에서 소개된 예제에 따르면, 요리 2개가 담긴 조합에 대한 탐색이 끝났다면, 그 다음인 요리 3개가 담긴 조합을 찾으며 p.second가 최대인 조합을 찾는 것이다.

이 때, set<char>을 string으로 변환하는 함수에서 sort를 수행해주고, 마지막으로 구한 answer 배열로 마찬가지로 sort해주어 문제의 조건을 맞춘다.

string make_string(const set<char> s){
    string result = ""; 
    for(char c : s)
        result.push_back(c); 
    sort(result.begin(), result.end()); 
    return result; 
}

✊ 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set> 
#include <iostream>
using namespace std;

void findCombination(string order, int index, string& result, set<set<char>>& combinations) {
    if (index == order.size()) {
        if (result.size() >= 2){
            set<char> s;
            for(char c : result)
                s.insert(c); 
            combinations.insert(s); 
        }
        return;
    }
    result.push_back(order[index]);
    findCombination(order, index + 1, result, combinations);
    result.pop_back();
    findCombination(order, index + 1, result, combinations);
}

string make_string(const set<char> s){
    string result = ""; 
    for(char c : s)
        result.push_back(c); 
    sort(result.begin(), result.end()); 
    return result; 
}

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

    set<set<char>> combinations;
    for (string order : orders) {
        string result; 
        findCombination(order, 0, result, combinations);
    }

    // 각 조합이 주문된 횟수를 구한다. 
    map<set<char>, int> mp;
    for (auto& p : mp)
        p.second = 0;

    for (auto combi : combinations) {
        for (string order : orders) {
            bool flag = true;
            for(char c : combi){
                if(order.find(c) == string::npos) {
                    flag = false; 
                    break;
                }
            }
            if(flag) mp[combi]++;
        }
    }

    // 각 조합이 등장한 횟수의 최댓값을 구한다.
    vector<string> answer;
    for(int x : course){
        int max = 0;
        vector<string> tmp; 
        cout << "x : " << x << endl;
        for (const auto& p : mp) {
            if (p.first.size() == x) {
                if (p.second > max) {
                    max = p.second;
                    tmp.clear();
                    if(mp[p.first] >= 2)
                        tmp.push_back(make_string(p.first));
                }
                else if (p.second == max){
                     if(mp[p.first] >= 2)
                        tmp.push_back(make_string(p.first));
                }
            }
        }

        for(string s : tmp)
            answer.push_back(s);
    }
    sort(answer.begin(), answer.end()); 
    return answer;
}

 

👩‍💻 고찰

최댓값이 여러 개일 경우, 모든 최댓값의 위치를 구하는 방법을 새롭게 배울 수 있었다. 

vector<int> arr = {1, 2, 3, 6, 6, 6}; 

int max = 0;
vector<int> answer; 
for(int i = 0; i < arr.size(); i++){
	if(arr[i] > max){
    	max = arr[i]; 
        answer.clear(); 
        answer.push_back(i);
    } else if(arr[i] == max)
    	answer.push_back(i);
}

 

프로그래머스에서 다른 사람의 풀이를 참고하였는데, 나는 처음부터 모든 조합을 구해서 map에 넣은 반면, 애초에 course 배열에서 요구된 개수만큼만 조합을 구하고 주문 횟수의 최댓값을 저장한 코드가 있어서 들고와보았다. 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

map<string, int> combi;

/* 주문한 메뉴(src)들을 기반으로, 메뉴 개수 (depth) 만큼 만들 수 있는 모든 조합 (crs) 을 만들어 map (combi) 에 저장한다. */ 
void combination(string src, string crs, int depth) {
    if (crs.size() == depth) combi[crs]++;
    else
        for (int i = 0; i < src.size(); i++)
            combination(src.substr(i + 1), crs + src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer; 
    for (string& order : orders)
        sort(order.begin(), order.end()); 

    for (int crs : course) {
        for (string order : orders)
            combination(order, "", crs); 

        int sup = 0; 
        for (auto it : combi) // 주문한 조합의 최대 개수를 구한다.
            sup = max(sup, it.second);
        for (auto it : combi) // 2명 이상 주문한 조합에 대해서 최대 개수인 조합을 저장한다.
            if (sup >= 2 && it.second == sup)
                answer.push_back(it.first); 
        combi.clear(); 
    }
    sort(answer.begin(), answer.end()); 
    return answer;
}