컴공 일기274

https://school.programmers.co.kr/learn/courses/30/lessons/72411

카카오 코딩테스트 문제답습니다.

소위 코딩 근육을 묻는 문제같네요.

해시, 재귀, 조합, 문자열 파싱, 최대최소 

각종 요소들이 복합적으로 어우러져 있습니다..

이런 문제는 구현하는데 시간 좀 잡아먹습니다.

많게는 2-3시간 걸릴 법한 문제죠.

#include <string>

#include <vector>

#include <unordered_map>

#include <algorithm>

using namespace std;

unordered_map<string, int> course_map;

void generateCombinations(const string& str, string current, int index, int k)

{

    if(current.size() == k)

    {

        course_map[current]++;

        return;

    }

    if(index == str.size()) return;

    //include

    generateCombinations(str, current+str[index], index+1, k);

    //not include

    generateCombinations(str, current, index+1, k);

}

vector<string> solution(vector<string> orders, vector<int> course) {

    vector<string> answer;

    unordered_map<int, string> menu_map;

    for(auto& order : orders)

    {

        sort(order.begin(), order.end());

    }

    //initialization of menu_map

    for(int i=0; i<orders.size(); i++)

    {

        menu_map[i] = orders[i];

    }

    //initialization of course_map

    for(const auto& course_length : course)

    {

        course_map.clear();

        for(const auto& order : orders)

        {

            if(order.size() >= course_length)

            {

                generateCombinations(order, "", 0, course_length);

            }

        }

        int max_count = 0;

        for(const auto& [key, value] : course_map)

        {

            if(value > max_count)

            {

                max_count = value;

            }

        }

        if(max_count >= 2)

        {

            for(const auto& [key, value] : course_map)

            {

                if(value == max_count)

                {

                    answer.push_back(key);

                }

            }

        }    

    }

    sort(answer.begin(), answer.end());

    return answer;

}