2021 KAKAO BLIND RECRUITMENT-메뉴 리뉴얼-C++

간단한 완전탐색,BackTracking,조합
완탐, BackTracking, 조합 그 무엇을 써도 좋다.
문제바로가기

풀이법

1. 모든 조합 만들기
   abcdef라면, 2,3,4에서 나올 수 있는조합은
   2: ab,ac,ad,ae,af,bc,bd,be,,,
   3: abc,abd,abe,abf,acd,ace,acf,ade,,,
   4:abcd,abce,abcf,acde,,,
   이런식이다 이런 조합을 우선 모두 만든다.
   조합을 사용할때 쓰는 퍼뮤테이션을 사용해도 되지만, 백트래킹에 익숙해지기 위해서 이번에는 백트래킹을 사용하였다.

2. 이 모든 조합의 문자 길이에서 제일 많이 주문한 조합을 구한다.

3. 이걸 오름차순으로 정리하고 answer vector에 넣는다.

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0;i<orders.size();i++){
        string tmp = orders[i];
        sort(tmp.begin(),tmp.end());
        for(int j=0;j<course.size();j++){
            make_combi(tmp,course[j],0);
        }
    }
    ...
    
void make_combi(string s, int cnt, int tmp){
    if(cnt==v.size()){
        mycheck();
        return;
    }
    
    for(int i = tmp; i<s.size(); i++){
        v.push_back(s[i]);
        make_combi(s,cnt,i+1);
        v.pop_back();
    }
}

간단하게 cnt인 course의 size만큼 확인하고 mycheck로 보낸다.

void mycheck(){
    string combi="";
    for(int i=0;i<v.size();i++){
        combi+=v[i];
    }
    
    int flag=0;
    for(int i=0;i<table.size();i++){
        if(table[i].first==combi){
            table[i].second++;
            flag=1;
        }
    }
    if(flag==0){
        table.push_back({combi,1});
    }
}

mycheck에서는 조합식이 몇번을 불렸는지 확인해야한다. table을 순회하면서, first가 조합으로 동일하면 second를 ++하고
만약에 flag가 0이면 현재 table에 없으므로, 새롭게 table에 넣어준다.

 
    for(int i=0;i<table.size();i++){
        string s = table[i].first;
        int cnt = table[i].second;
        int s_size = s.size();
        if(cnt>=2){
          //크거나, 같은경우
          if(mymax[s_size]<cnt){
            find_max[s_size].clear();
            find_max[s_size].push_back(s);
            mymax[s_size]=cnt;
          }else if(mymax[s_size]<=cnt){
            find_max[s_size].push_back(s);    
          }
        }
    }
    
    map<string,int>m;
    for(int i=0;i<course.size();i++){
        if(find_max[course[i]].size()>0){
            for(int j=0;j<find_max[course[i]].size();j++){
                m[find_max[course[i]][j]]=0;
            }
        }
    }
    
    for (auto iter : m) {
        answer.push_back(iter.first);
    }
    
    return answer;

마지막으로 제일 많이 불린 조합을 찾아내는것이다.
cnt>=2로 두번이상 주문했는지 확인하고, 그다음에 cnt가 mymax에 있는 값보다 크면 갱신해야하므로 find_max를 전부지우고 push하고
그게 아니라 동일하면 그냥 push한다.

그 다음에 오름차순으로 정렬해야하므로, map에다가 다시 넣은다음 m에서 값을 다시 꺼내서 answer에 넣어준다.

정답코드

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

vector<char>v;
vector<pair<string,int>>table;
vector<string> find_max[11];
int mymax[30]={0,};

void mycheck(){
    string combi="";
    for(int i=0;i<v.size();i++){
        combi+=v[i];
    }
    
    int flag=0;
    for(int i=0;i<table.size();i++){
        if(table[i].first==combi){
            table[i].second++;
            flag=1;
        }
    }
    if(flag==0){
        table.push_back({combi,1});
    }
}


void make_combi(string s, int cnt, int tmp){
    if(cnt==v.size()){
        mycheck();
        return;
    }
    
    for(int i = tmp; i<s.size(); i++){
        v.push_back(s[i]);
        make_combi(s,cnt,i+1);
        v.pop_back();
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0;i<orders.size();i++){
        string tmp = orders[i];
        sort(tmp.begin(),tmp.end());
        for(int j=0;j<course.size();j++){
            make_combi(tmp,course[j],0);
        }
    }
    
    for(int i=0;i<table.size();i++){
        //cout<<table[i].first<<" "<<table[i].second<<"\n";
        string s = table[i].first;
        int cnt = table[i].second;
        int s_size = s.size();
        if(cnt>=2){
          //크거나, 같은경우
          if(mymax[s_size]<cnt){
            find_max[s_size].clear();
            find_max[s_size].push_back(s);
            mymax[s_size]=cnt;
          }else if(mymax[s_size]<=cnt){
            find_max[s_size].push_back(s);    
          }
        }
    }
    
    map<string,int>m;
    for(int i=0;i<course.size();i++){
        if(find_max[course[i]].size()>0){
            for(int j=0;j<find_max[course[i]].size();j++){
                m[find_max[course[i]][j]]=0;
            }
        }
    }
    
    for (auto iter : m) {
        answer.push_back(iter.first);
    }
    
    return answer;
}