[프로그래머스]메뉴 리뉴얼 (C++ / 2021 KAKAO BLIND)

메뉴 리뉴얼 (Level 2)

문제

전체 문제 보기

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

접근법

이 문제는 Brute force 방식으로 모든 조합을 계산해서 풀어야 하는 문제입니다. order 하나의 최대 길이가 10으로 충분히 작기 때문에 모든 경우의 수를 따져볼 수 있습니다. 모든 조합의 경우의 수를 만들기 위해서는 백트래킹을 사용할 수 있습니다. (백트래킹에 대한 이해가 필요하다면 이 글을 참고해주세요)

 

백트래킹을 사용하여 문제를 풀기 위해서 아래와 같이 길이별로 해시 테이블을 11개 생성했습니다. (2 ~ 10까지 사용할 예정입니다.) 또한 한번 탐색한 조합은 hash set에 등록하여 중복 탐색을 막을 수 있습니다.

// 길이별 메뉴 테이블
array<unordered_map<string, int>, 11> menus;
// 탐색한 조합을 체크하기 위한 hash set
unordered_set<string> isChecked;

전체 구현

백트래킹 함수에서는 깊이가 order 문자열에 인덱스를 활용하여 문자를 하나씩 추가하는 방식으로 구현할 수 있습니다. 자세한 사항은 주석을 참고해주세요.

#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
using namespace std;

// 길이별 메뉴 테이블
array<unordered_map<string, int>, 11> menus;
// 탐색한 조합을 체크하기 위한 hash set
unordered_set<string> isChecked;

void BackTracking(string& order, int len, string& newMenu, int depth, int index)
{
    // 한번 검사한 조합은 더 이상 검사하지 않음
    if (isChecked.find(newMenu) != isChecked.end()) return;
    isChecked.insert(newMenu);

    if (depth == len)
    {
        menus[len][newMenu]++;
        return;
    }

    for(int i = index; i < order.size(); ++i)
    {
        char ch = order[i];
        newMenu.push_back(ch);  

        // 인덱스를 1 더크게 전달하여 중복된 문자가 추가되는것을 막는다.
        // 깊이를 1씩 추가하여 현재 문자열의 길이를 표현할 수 있다.
        BackTracking(order, len, newMenu, depth + 1, i + 1);
        newMenu.pop_back();
    }
}

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

    string newMenu ("");
    for (string& order : orders)
    {
        sort(order.begin(), order.end());
        for (int len : course)
        {
            // 코스 크기 보다 주문수가 적다면 continue
            if (order.length() < len) continue;

            // 모든 주문들을 코스의 개수만큼 백트래킹 탐색.
            // 탐색결과는 menus 배열에 기록된다.
            BackTracking(order, len, newMenu, 0, 0);
            isChecked.clear(); // 탐색한 조합을 체크하기 위한 hash set 초기화
        }
    }

    // 메뉴 크기별 가장 많은 주문을 받은 메뉴를 탐색하여 answer 배열에 추가
    for (int len : course)
    {
        int best{};
        for (auto menu : menus[len])
        {
            best = max(best, menu.second);
        }
        for (auto menu : menus[len])
        {
            if (menu.second == best && best > 1)
            {
                answer.push_back(menu.first);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}