[알고리즘 풀이 분석] 프로그래머스 2021 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼

오늘 풀어본 문제는 메뉴 리뉴얼 이다. 백준 슬슬 질려서 오랜만에 프로그래머스에서 찾아보았다!
사실 어제 시작 했는데,,, 뭐 암튼 그렇게 됐다 ^^,,
카카오 코테가 이제 한 2주 정도밖에 남지 않아서 이번주 부터는 카카오 기출을 중점적으로 쭉 풀어볼 생각이다. 아무래도 카카오 시험이 길기도 길고 두번이나 보고,, 난이도도 있는 편이니까

2021 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

입출력

• 입출력 예 #1
  문제의 예시와 같습니다.

• 입출력 예 #2
  AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
  요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

• 입출력 예 #3
  WX가 두 번, XY가 두 번 주문됐습니다.
  3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
  또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

나의 풀이

특별히 사용한 알고리즘이나 아이디어는 없는 문제였다! 이런저런 조건을 잘 생각해서 구현해야 하는Implementation 문제라고 생각했고 빠진 조건 없이 꼼꼼히 구현하려고 했다!

입력된 주문 종류와 출력되는 코스들을 보면 26가지 메뉴가 모두 독립적임을 알 수 있다. 때문에 입력되는 주문 마다 각 메뉴들을 대상으로 가능한 조합들을 먼저 알아내야 한다. 예를들어 "ABC" 가 입력되면 이 때 가능한 조합은 "AB", "AC", "BC" 이다.

또 세번째 예제 입출력에서 "XWY", "WXA" 이 입력되었지만 출력에는 "WX" 만이 존재하는 것을 보면 각 메뉴에 순서는 상관이 없음을 알 수 있다.

구한 각 조합들이 담긴 배열 combinations 의 각 조합 별로 몇번씩 출현 했는지를 count 한다. 나는 이 과정에서 orders.size() * 27 의 크기를 가지는 2차원 배열 orderCheck 를 이용했는데 orderCheck 에는 주문된 메뉴들이 체크되어 있다. 예를 들어, order[i] 가 "AB" 라면 orderCheck[i][1], orderCheck[i][2] 가 true 이다.

각 조합별로 모든 메뉴에서 몇번 주문되는지를 센 이후에 이를 combinations[i].second 에 저장한다. 또한 이 과정에서 각 코스 길이별로 제일 많이 주문된 조합은 몇번 나오는지를 저장해 두었다.

이후에는 second 값까지 완성된 combinations 에서 각 코스 길이별로 가장 많이 주문된 메뉴 조합을 answer 에 담으면 된다.

코드

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

// 프로그래머스 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼, level 2
using namespace std;

bool byLength(string a, string b){
    if (a.size() != b.size()){
        return a.size() < b.size();
    }
    return a<b;
}

bool byPairLength(pair<string, int> a, pair<string, int> b){
    if (a.first.size() != b.first.size()){
        return a.first.size() < b.first.size();
    }
    return a.first<b.first;
}

bool byLenghtAndCount(pair<string, int> a, pair<string, int> b) {
    if (a.first.size() == b.first.size()){
        return a.second > b.second;
    }else{
        return a.first.size() < b.first.size();
    }
}


// alphabets 에서 r개를 뽑는 조 구하기 
void getCombination(vector<char> alphaets, int r, vector<pair<string, int>> & combinations){
    int n = alphaets.size();

    vector<bool> select(n-r, false);
    for (int i = 0; i < r; ++i) {
        select.push_back(true);
    }

    do{
        string combi = "";
        for (int i = 0; i < n; ++i) {
            if (select[i]){
                combi += alphaets[i];
            }
        }
        combinations.push_back(make_pair(combi, 0));
    }while (next_permutation(select.begin(), select.end()));
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    sort(orders.begin(), orders.end(), byLength);
    
    // 가능한 조합과 그 조합의 주문 횟수 저장 배열 
    vector<pair<string, int>> combinations;  
    
    // 각 주문별로 주문된 메뉴 체크 배열 
    vector<vector<bool>> orderCheck(orders.size(), vector<bool>(27, false));

    for (int i = 0; i < orders.size(); ++i) {
        vector<char> alphabets;
        
        // 주문별로 주문된 메뉴 내에서 가능한 조합 구하기 
        for (int j = 0; j < orders[i].size(); ++j) {
            alphabets.push_back(orders[i][j]);
            orderCheck[i][orders[i][j]-64] = true;
        }
        sort(alphabets.begin(), alphabets.end());

        for (int j = 0; j < course.size(); ++j) {
            if (course[j] <= orders[i].size()){
                getCombination(alphabets, course[j], combinations);
            }
            else break;
        }
    }

    // 조합에서 중복 제거
    sort(combinations.begin(), combinations.end(), byPairLength);
    combinations.erase(unique(combinations.begin(), combinations.end()), combinations.end());

    int maxLen = course[course.size()-1];
    vector<int> maxCount(maxLen+1, -1);

    for (int i = 0; i < combinations.size(); ++i) {
        int count = 0;
        int courseLen = combinations[i].first.size();

        // 각 조합 * 각 주문 별로 해당 조합이 주문되었는지를 count 
        for (int j = 0; j < orders.size(); ++j) {
            if(courseLen <=  orders[j].size()){
                bool same = true;
                for (int k = 0; k < courseLen; ++k) {
                    if (!orderCheck[j][combinations[i].first[k]-64]){
                        same = false;
                        break;
                    }
                }
                if (same) count++;
            }
        }
        combinations[i].second = count;
        
        // 2번 이상 주문된 경우 최대 주문 횟수 저장 
        if(count >= 2 && count > maxCount[courseLen]) maxCount[courseLen] = count;
    }

    sort(combinations.begin(), combinations.end(), byLenghtAndCount);


    // 각 조합 길이별로 최대 주문 조합 저장하기 
    for (int i = 0; i < combinations.size(); ++i) {
        int len = combinations[i].first.size();
        if (combinations[i].second == maxCount[len]){
            answer.push_back(combinations[i].first);
        }
    }
    sort(answer.begin(), answer.end());

    return answer;
}