[프로그래머스] level2 메뉴 리뉴얼 (C++)

2021 카카오 블라인드 채용

 

 

문제를 읽어봤는데 요구사항을 한 번에 이해하지 못했다. 카카오 문제 특징인 것 같다. 지문이 너무 길다..

그래서 처음 풀때는 시간내에 풀지 못하고 풀이만 어렴풋이 생각해둔채로 넘겼었다.

 

다시 풀기위해서 차분하게 풀이를 머릿속에 모두 정리하고 코딩에 들어갔다.

개인적으로 깔끔하게 풀린것같아서 마음에 드는 코드이다.

 

 

먼저 orders로 들어온 string을 오름차순 정렬하기 위해서 char로 모두 분해한 다음에 알파벳 순으로 정렬해서 2차원 벡터 형태로 만들어줬다.

vector< vector<char> > norders;
    for(auto str: orders){
        vector<char> temp;
        for(int i = 0; i < str.size(); i++){
            temp.push_back(str[i]);
        }
        sort(temp.begin(), temp.end());
        norders.push_back(temp);
    }

 

각 손님이 주문한 메뉴의 조합을 모두 만들어본다. 

for(int i = 0; i < norders.size(); i++){
        for(int j = 0; j < course.size(); j++){
            dfs(0, 0, course[j], norders[i], "");
        }
    }

 

메뉴의 조합이 끝나면 

현재 코스가 몇 개의 메뉴로 구성되었는지 알기 때문에

해당 갯수에 맞는 map의 현재 코스를 주문한 횟수를 +1 해준다.

아직 현재 코스가 2번 이상 나오지 않았다면 넘어간다.

if(now == cnt){
    int now_cnt = ++mp[cnt][course];
    if(now_cnt < 2) return;

 

만약 2번 이상 나왔다면,

현재 코스의 주문 횟수가 최댓값을 갱신하게 된다면, 코스를 구성하는 메뉴 갯수에 따른 최댓값을 갱신하고, 최댓값에 포함되었던 코스를 포함하는 벡터를 초기화 하고, 새롭게 구성된 코스를 벡터에 추가한다.

if(now_cnt > max_order[cnt]){
    max_order[cnt] = now_cnt;
    courseMenu[cnt].clear();
    courseMenu[cnt].push_back(course);
}

 

나온 횟수가 최댓값과 동일하다면,

횟수에 해당하는 벡터에 코스를 추가한다.

else if(now_cnt == max_order[cnt]){
    courseMenu[cnt].push_back(course);
}

 

 

최종적으로 원하는 코스 개수에 맞는 답을 추려내여 answer벡터에 모으고, 정렬 후 반환하면 답을 구할 수 있다.

for(int i = 0; i < course.size(); i++){
    for(auto &w: courseMenu[course[i]]){
        answer.push_back(w);
    }
}
sort(answer.begin(), answer.end());
return answer;

 

 

 

전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

map<int, map<string, int> > mp;

int max_order[11];
vector<string> courseMenu[11];

void dfs(int idx, int now, int cnt, vector<char> &menu, string course){
    if(now == cnt){
        int now_cnt = ++mp[cnt][course];
        if(now_cnt < 2) return;
        
        if(now_cnt > max_order[cnt]){
            max_order[cnt] = now_cnt;
            courseMenu[cnt].clear();
            courseMenu[cnt].push_back(course);
        }
        else if(now_cnt == max_order[cnt]){
            courseMenu[cnt].push_back(course);
        }
        
        return;
    }
    
    for(int i = idx; i < menu.size(); i++){
        dfs(i+1, now+1, cnt, menu, course+menu[i]);
    }
}


vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    vector< vector<char> > norders;
    for(auto str: orders){
        vector<char> temp;
        for(int i = 0; i < str.size(); i++){
            temp.push_back(str[i]);
        }
        sort(temp.begin(), temp.end());
        norders.push_back(temp);
    }
    
    for(int i = 0; i < norders.size(); i++){
        for(int j = 0; j < course.size(); j++){
            dfs(0, 0, course[j], norders[i], "");
        }
    }
    
    for(int i = 0; i < course.size(); i++){
        for(auto &w: courseMenu[course[i]]){
            answer.push_back(w);
        }
    }
    sort(answer.begin(), answer.end());
    
    return answer;
}