[완전탐색] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT

해결 방법

단품 메뉴 조합에서 2개 이상을 고른 모든 조합을 모두 추출하고, 나타난 조합의 빈도를 계산하면 된다. map을 이용하면 이를 쉽게 계산할 수 있을 것이다.

<algorithm>의 next_permutation() 함수를 이용하면 간단하게 모든 조합을 구할 수 있다. 사용 방법은 아래 포스팅을 참고하길 바란다.

https://kimcoder.tistory.com/118

next_permutation을 이용한 조합 구현

모든 조합의 결과는 조합된 단품 메뉴의 개수별로 분류해서 저장하고, 각 단품 메뉴의 개수별로 빈도수가 가장 높은 주문 조합을 모두 answer에 저장한 뒤에 answer을 오름차순 정렬하면 정답을 구할 수 있다.

 

 

소스 코드

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

vector<int> arr; // 순열 요소
vector<bool> check; // 순열 인덱스
vector<string> courses[11]; // 단품 메뉴의 수에 따른 코스
map<string, int> m; // 조합 별 주문 수
map<string, int>::iterator iter;

void set_check(int n, int r){
    for(int i=0;i<r;i++) check.push_back(true);
    for(int i=r;i<n;i++) check.push_back(false);
}

void combination(int n) {
    do{
        string s="";
        for(int i=0;i<n;i++) if(check[i]) s+=(arr[i]+'0');
        m[s]++;
    } while(next_permutation(check.begin(),check.end()));
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // 조합 연산
    for(int i=0;i<orders.size();i++){
        sort(orders[i].begin(), orders[i].end());
        arr.clear();
        int slen = orders[i].length();
        for(int j=0;j<slen;j++) arr.push_back(orders[i][j]-'0');
        for(int j=2;j<=slen;j++) {
            set_check(slen,j);
            sort(check.begin(), check.end());
            combination(slen);
            check.clear();
        }
        
    }
    
    // 조합된 단품 메뉴의 개수별로 분류해서 저장
    for(iter=m.begin();iter!=m.end();iter++) courses[iter->first.length()].push_back(iter->first);
    
    // 코스요리의 메뉴 구성
    int maxi;
    for(int i:course) { // 조합된 단품 메뉴의 개수별로 수행
        maxi=0;
        for(int j=0;j<courses[i].size();j++) if(m[courses[i][j]]>maxi) maxi=m[courses[i][j]]; // 최대 주문 수 계산
        if(maxi<2) break;
        for(int j=0;j<courses[i].size();j++) if(m[courses[i][j]]==maxi) answer.push_back(courses[i][j]); // 최대 주문 조합 저장
    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

테스트케이스 20개 모두 정답

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72411