[프로그래머스] 메뉴 리뉴얼

2021 카카오 코딩 테스트 문제입니다.

 

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

문제 확인

 

조합과 자료구조를 사용하는 문제입니다.

 

풀이

 

dfs로 메뉴 조합을 찾을 수 있지만 최대 depth가 10이고 손님마다 dfs를 모두 돌면 많은 시간이 걸리기 때문에 조합을 찾는 특별한 알고리즘을 사용합니다.

파이썬에서 사용하는 combination 함수를 구현하여 사용합니다. combination 함수는 permutation 방식을 사용하여 조합을 구하는 방식이며 std::next_permutation 함수를 사용합니다.

next_permutation - C++ Reference

Steinhaus-Johnson-Trotter 알고리즘을 사용한 방식이며 일반적인 dfs에 비교하여 더 빠르게 조합을 구해낼 수 있습니다.

 

조합을 구한 후 map 컨테이너에 저장하여 메뉴 조합이 나오는 횟수를 기록합니다. 이때 course 크기에 해당하는 메뉴마다 최대 횟수를 기록해 마지막 탐색 시 1번의 탐색으로 결과를 낼 수 있도록 합니다.

모든 사람의 메뉴를 기록하고 나면 course 마다 기록해둔 최댓값을 사용해 결과를 찾아냅니다.

 

코드

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
 
using namespace std;
 
vector<string> combination(string input, int r) {
    int n = input.size();
    if (n < r || r < 0) return {};
    vector<string>res;
    string tmp;
    tmp.resize(r);
 
    vector<bool> per(n);
    fill(per.end() - r, per.end(), true);
 
    do {
        int cur = 0;
        for (int i = 0; i < n; ++i)
            if (per[i])
                tmp[cur++] = input[i];
 
        res.emplace_back(tmp);
    } while (next_permutation(per.begin(), per.end()));
 
    return res;
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<map <string, int>> menu(course.size());
    vector<int> max_val(course.size());
    vector<string> answer;
    for (auto &str : orders) {
        sort(str.begin(), str.end());//XY, YX 경우 같은 조합이므로 이와같은 경우를 처리해주기 위함
        for (int i = 0; i < course.size();i++) {
            if (course[i] > str.size())break;
            auto comb = combination(str, course[i]);//조합 만들기
            for (auto &t : comb) {
                auto res = menu[i].insert({ t, 1 });//조합 추가
                if (!res.second) {//이미 조합이 있는 경우
                    res.first->second++;//횟수를 늘림
                    max_val[i] = max_val[i] < res.first->second ? res.first->second : max_val[i];//최댓값 기록
                }
                    
            }
        }
    }
    for (int i = 0; i < course.size(); i++) {
        for (auto &t : menu[i]) {
            if (t.second == max_val[i])
                answer.emplace_back(t.first);//결과 기록
        }
    }
 
    sort(answer.begin(), answer.end());//정렬
    return answer;
}
 
int main() {
    vector<string> o = { "XYZ", "XWY", "WXA" };
    vector<int> c = { 2,3,4 };
    auto v = solution(o, c);
    for (auto t : v)
        cout << t << ' ';
}
 
/*
{"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}    {2,3,4}    {"AC", "ACDE", "BCFG", "CDE"}
{"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"}    {2,3,5}    {"ACD", "AD", "ADE", "CD", "XYZ"}
{"XYZ", "XWY", "WXA"}    {2,3,4} {"WX", "XY"}
 
테스트 1 〉    통과 (0.07ms, 3.95MB)
테스트 2 〉    통과 (0.05ms, 3.96MB)
테스트 3 〉    통과 (0.07ms, 3.91MB)
테스트 4 〉    통과 (0.07ms, 3.97MB)
테스트 5 〉    통과 (0.07ms, 3.94MB)
테스트 6 〉    통과 (0.15ms, 3.9MB)
테스트 7 〉    통과 (0.16ms, 3.94MB)
테스트 8 〉    통과 (1.47ms, 3.93MB)
테스트 9 〉    통과 (0.92ms, 3.73MB)
테스트 10 〉    통과 (1.40ms, 3.93MB)
테스트 11 〉    통과 (0.76ms, 3.92MB)
테스트 12 〉    통과 (0.94ms, 3.94MB)
테스트 13 〉    통과 (1.31ms, 3.98MB)
테스트 14 〉    통과 (0.83ms, 3.96MB)
테스트 15 〉    통과 (1.33ms, 3.93MB)
테스트 16 〉    통과 (0.33ms, 3.9MB)
테스트 17 〉    통과 (0.18ms, 3.85MB)
테스트 18 〉    통과 (0.07ms, 3.96MB)
테스트 19 〉    통과 (0.02ms, 3.97MB)
테스트 20 〉    통과 (0.20ms, 3.97MB)
*/