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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/72411

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

2020년 하반기에 진행됐던 '2021 KAKAO Blind Recruitment' 기출문제입니다.

개인적으로 이 문제는 Level 2가 아닌 것 같습니다... Level 3 정도는 되어야할듯 합니다 ㅠㅠ

 

기본적으로는 탐색을 이용하여 가능한 경우의 수 중 특정 조건을 만족하는 경우를 찾는 것입니다.

문제가 길어서 요구조건을 이해하기 어려운데, 요약하면 다음과 같습니다.

 

• 한 사람이 음식을 2개 이상 주문했을 때, 주문한 음식의 원소를 2개 이상 가지는 부분집합을 '코스요리' 라고 합니다.
  
  • 예를 들어, 한 사람이 음식 A, B, C를 주문했다면, 가능한 코스요리의 종류는 {A, B}, {B, C}, {A, B, C} 세 가지 가 됩니다.
• 모든 가능한 코스요리 중 2번 이상 주문된 코스요리만을 고려합니다. 즉, 1번만 주문된 코스요리는 고려하지 않습니다.
• course 배열에 주어진 각 숫자는 '코스요리에 포함된 단품 음식의 수' 를 의미합니다.
• 이 때, 각 course 배열에 주어진 값마다 가장 주문이 많이 된 코스 요리를 구하세요.
  • course = [2, 3, 5]라면, 음식의 수가 2, 3, 5개인 각각의 코스요리 경우에 대해 가장 많이 주문된 코스요리를 구합니다.
  • 가장 많이 주문된 코스요리가 2개 이상일 경우, 전부 정답에 포함됩니다.

맨 처음으로, 저는 탐색을 쉽게 하기 위해, 각 주문 내용의 원소를 unordered set에 등록하였습니다.

vector<unordered_set<char> > order_set을 선언하고 사용하였는데, 이렇게 하면 코스요리가 각 주문마다 포함되었는지 훨씬 빠르게 탐색할 수 있다고 판단하였습니다 (unordered set은 O(1)의 탐색시간을 가지므로).

 

다음으로, course의 각 원소 i에 대해, 모든 코스요리 조합 중 길이 i를 가지는 경우를 탐색하였습니다.

이를 위해 dfs를 통해 길이 i의 문자열을 만들었는데, 문자열을 만든 후보는 각각의 orders 목록입니다.

즉 각 orders별로 길이 i를 가지는 코스요리를 만들었습니다.

맨 처음에는 주어진 문제에서 주문된 모든 단품 요리를 가지고 모든 경우의 수를 만들어 탐색했는데, 이렇게 했더니 시간 초과에 걸렸습니다.

 

만들어진 길이 i의 문자열을 가지고, 우선 정렬을 한 후에, 중복으로 탐색되는 것을 방지하기 위하여 unordered_set<string> trial을 선언하고 사용하였습니다.

정렬을 한 이유는 코스요리 'AC'와 'CA'를 구분하기 위함이며, 'AC'가 두 번 탐색되는 것을 방지하기 위해 중복을 허용하지 않는 자료구조 set을 사용하였습니다.

 

다음으로, 함수 combination_check을 이용하여, 각 orders가 코스요리 combination의 모든 원소를 포함하는 경우를 세었습니다.

만약 세어진 횟수가 2번 이상이라면, 해당 코스 요리가 2번 이상 주문되었다는 의미가 됩니다. 따라서 정답 후보 배열 answer_sub에 {count, combination} 형식으로 담았습니다.

 

이렇게 모인 정답 후보 중에서, 각각 count를 기준으로 내림차순 정렬을 한 후, course의 각 원소 i마다 가장 count가 높은 원소들을 answer에 담고, answer를 정렬하여 답을 얻었습니다.

 

코드 링크: GitHub

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

vector<vector<pair<int, string > > > answer_sub(11);
unordered_set<string> trial;

bool sub_sort(pair<int, string> a, pair<int, string> b) {
    return a.first > b.first;
}

void combination_check(string combination, vector<unordered_set<char> > &order_set) {
    
    int count = 0;
    
    // 각 주문한 케이스에 대해, 만들어낸 조합을 포함하는 케이스가 몇 개인지 센다.
    for (int i = 0; i < order_set.size(); i++) {
        bool all_exists = true;

        for (int j = 0; j < combination.size(); j++) {
            if (order_set[i].find(combination[j]) == order_set[i].end()) {
                all_exists = false;
                break;
            }
        }
        if (all_exists) count++;
    }
    if (count >= 2) {
        sort(combination.begin(), combination.end());
        answer_sub[combination.size()].push_back({count, combination});
    }
}

void menu_combination(int j, string &orders, int course_length, unordered_set<char> visited, string combination, vector<unordered_set<char> > &order_set) {
    
    // 조합 구성이 다 되었으면, 중복 여부를 검사하고, 2번 이상 주문되었는지 확인한다.
    if (visited.size() == course_length) {
        sort(combination.begin(), combination.end());
        if (trial.find(combination) == trial.end()) {
            trial.insert(combination);
            combination_check(combination, order_set);
            return;
        }
    }
    else if (visited.size() > orders.size()) return;
    
    // 조합 구성을 마저 한다.
    else {
        string nextCombination = combination;
        for (int i = j; i < orders.size(); i++) {
            char current = orders[i];
            if (visited.find(current) == visited.end()) {
                visited.insert(current);
                nextCombination += current;
                menu_combination(i, orders, course_length, visited, nextCombination, order_set);
                visited.erase(current);
                nextCombination = combination;
            }
        }
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    
    vector<unordered_set<char> > order_set(orders.size());

    for (int i = 0; i < orders.size(); i++) {
        for (int j = 0; j < orders[i].size(); j++) {
            order_set[i].insert(orders[i][j]);
        }
    }
    
    // i번 주문된 단품메뉴 조합을 찾는다.
    for (int i = 0; i < course.size(); i++) {
        unordered_set<char> visited;
        string combination = "";
        
        for (int a = 0; a < orders.size(); a++) {
            for (int j = 0; j < orders[a].size(); j++) {
                visited.insert(orders[a][j]);
                combination += orders[a][j];
                // i개의 단품메뉴로 이루는 조합 구성 시작
                menu_combination(j, orders[a], course[i], visited, combination, order_set);
                visited.erase(orders[a][j]);
                combination = "";
            }
        }
    }
    
    vector<string> answer;
    
    for (int i = 0; i < course.size(); i++) {
        sort(answer_sub[course[i]].begin(), answer_sub[course[i]].end(), sub_sort);
        int most_ordered = answer_sub[course[i]][0].first;
        for (int j = 0; j < answer_sub[course[i]].size(); j++) {
            if (answer_sub[course[i]][j].first == most_ordered) {
                answer.push_back(answer_sub[course[i]][j].second);
            }
            else break;
        }
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

문제가 많이 길고, 고려해야 할 점도 많아서 푸는 시간이 오래 걸렸습니다 ㅠ

아마 지금이라도 이 문제를 코테에서 보게 됐다면... 이 문제를 푸느라 다른 문제를 못 건드렸을 것 같은 느낌이 강하게 드네요.

코테 연습 더 열심히 해야겠습니다.