(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 메뉴 리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411?language=cpp

코딩테스트 연습 - 메뉴 리뉴얼

backtracking으로 푼 문제였습니다.

 

풀이방법

 1. orders의 문자열 하나씩을 확인하여 정렬합니다. 이런식으로 정렬한다면 세번째 예제에서 'XWY'는 'WXY'로 정렬됩니다.

 2. map으로 모든 orders문자열들을 보면서 각 알파벳이 몇 개씩 나왔는지 세줍니다. 2개 이상나온 알파벳들을 합쳐 새로운 문자열 candidates를 만들어 줍니다.

 3. backtracking으로 candidates의 문자열들 중 course의 i번째 원소의 값만큼 뽑아주어 리스트에 넣어줍니다. 즉

candidates.size() C course[i]

가 됩니다.

 4. 가장 많이 주문된 문자열 리스트를 뽑아 answer에 넣어줍니다.

Code

#include <bits/stdc++.h>

using namespace std;
vector<string> tmp;

int getMenuCnt(string s, vector <string> &orders){
    int cnt = 0;
    for(int i = 0; i < orders.size(); i++){
        int pivot = 0;
        for(int j = 0; j < orders[i].size(); j++)
            if(orders[i][j] == s[pivot]) 
                pivot++;
        if(pivot == s.size()) cnt++;
    }
    return cnt;
}

vector <string> getMaxOrderedMenuList(vector <string> &orders){
    int maxMenuCnt = 0;
    vector<string> maxMenuList;
    for(auto &t : tmp) maxMenuCnt = max(maxMenuCnt, getMenuCnt(t,orders));

    for(auto &t : tmp)
        if(maxMenuCnt>=2 && getMenuCnt(t,orders) == maxMenuCnt) 
            maxMenuList.push_back(t);
    return maxMenuList;
}

void backTracking(int depth,int idx, int m, string s, string candidates){
    if(depth == m) {
        tmp.push_back(s);
        return;
    }
    for(int i = idx; i < candidates.size(); i++){
        backTracking(depth + 1, i + 1, m, s+candidates[i],candidates);
    }
}

string getCandidatesString(vector<string> orders){
    map <char,int> m;
    string candidates = "";
    for(auto &o : orders)
        for(int i = 0; i < o.size(); i++)
            m[o[i]]++;
    for(auto &a : m) 
        if(a.second >= 2) 
            candidates += a.first;
    return candidates;
}

void sortOrders(vector <string> &orders){
    for(auto &o : orders){
        vector<char> tmp;
        for(int i = 0; i < o.size(); i++) tmp.push_back(o[i]);
        sort(tmp.begin(),tmp.end());
        string s = "";
        for(auto &t : tmp) s += t;
        o = s;
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector <string> answer;
    sortOrders(orders);
    string candidates = getCandidatesString(orders);

    for(auto &c : course){
        tmp.clear();
        backTracking(0,0,c,"",candidates);
        vector <string> maxOrderedList = getMaxOrderedMenuList(orders);
        for(auto &mo : maxOrderedList) answer.push_back(mo);
    }
    
    sort(answer.begin(),answer.end());
    return answer;
}

// int main(){
//     vector <string> answer;
//     answer = solution({"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"},{2,3,4});
//     for ( auto &a : answer) cout << a << ' ';
// }